CF1346I Pac-Man 2.0

Polycarp 正在开发一款名为 “Pac-Man” 的经典游戏的新版本。尽管他非常喜欢原始版本的游戏，但他不喜欢其中的某些方面，因此决定稍微改变规则。 在 Polycarp 的版本中，你扮演 Pac-Man，在游戏世界中收集散落的豆子，同时避开危险的鬼魂（与原版没有区别）。Polycarp 不喜欢原版中没有逃脱鬼魂的机会，所以在他的版本中，游戏世界被分为 $n$ 个安全区域，之间有 $m$ 条单向路径连接——保证 Pac-Man 可以从任何一个安全区域到达另一个安全区域。由于安全区域是安全的，鬼魂无法在 Pac-Man 在那里时攻击它，它只有在穿越路径时才会受到威胁。Pac-Man 在安全区域 $s$ 中开始游戏。 所有的豆子都散落在安全区域；最初，第 $i$ 个安全区域包含 $a_i$ 个豆子（如果 Pac-Man 在安全区域中，它可以自由地收集其中的所有豆子）。被收集后，豆子会消失，但在游戏世界中的最后一个豆子被收集后，新的豆子会在安全区域中以相同数量重新生成（第 $i$ 个区域会重新生成 $a_i$ 个新豆子）。豆子可以无限次重新生成，所以这个游戏基本上是无限的。 Polycarp 已经确定了游戏世界的结构和每个安全区域中的豆子数量。现在他正在尝试判断游戏是否足够困难。游戏中有 $q$ 个目标，第 $i$个目标是从游戏开始时至少收集 $C_i$ 个豆子。Polycarp 将第 $i$ 个目标的难度定义为玩家必须遍历一条单向路径的最小次数，以收集 $C_i$ 个豆子（因为只有遍历路径时，Pac-Man 才会处于危险中）。如果 Pac-Man 在收集豆子时多次遍历某条路径，则该路径被计入答案的次数相同。 帮帮 Polycarp 计算出每个目标的难度吧！ ### **简明题意** 给定一张有向图，每个安全点有一定点权。对于每一个询问 $C$，输出为了使经过点权和大于等于 $C$，遍历一条单向路径的最小次数。

第一行包含四个整数 $n$，$m$，$q$ 和 $s$ $(2\le n\le 15；n\le m\leq n(n-1);1\le q\leq5000;1\le s\le n)$，分别表示安全区域的数量，路径的数量，目标的数量和起始安全区域的编号。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ $( 1 \le a_i\le 10^9 )$，其中 $a_i$ 是第 $i$ 个安全区域中初始颗粒数（以及当世界中最后一个颗粒被收集时在第 $i$ 个安全区域中重新生成生成的颗粒数）。 然后是 $m$ 行，每行包含两个整数 $v_i$ 和 $u_i$ $(1\le v_i ,u_i \le n ; v_i \ne u_i )$，表示从安全区 $v_i$ 到安全区 $u_i$ 的单向路径。每个有序对 $(v_i, u_i)$ 在此部分最多出现一次（从 $v_i$ 到 $u_i$ 没有多个路径），并且可以通过这些路径从一个安全区到达另一个安全区。 最后一行包含 $q$ 个整数 $C_1,C_2,...,C_q$ $( 1 \le C_i \le 10^{15})$，其中 $C_i$ 是玩家为了完成第 $i$ 个目标而必须收集的最小颗粒数。

对于每个目标 $i$，输出一个整数——它的难度（玩家至少需要沿某条路径行进的最小次数，以收集至少 $C_i$ 个豆子）。 ### **说明/提示** 考虑样例一。为了收集 $5$ 个小球，玩家应该在安全区域 $1$（即起始位置）收集 $3$ 个小球，然后移动到区域 $3$，在那里收集 $2$ 个小球。 为了收集 $8$ 个豆子，玩家应该在安全区 $1$ 收集 $3$ 个豆子，前往 $2$，收集 $1$ 个豆子，前往 $1$ 而不捡起豆子，前往 $3$，收集 $2$ 个豆子。现在地图上最后一个豆子被收集，所以它们会重新出现。玩家可以在安全区 $3$ 收集 $2$ 个豆子，现在收集的豆子数量是 $8$ 个。 再来看样例二。 为了收集 $7$ 颗小球，我们可以按照以下步骤进行：$2(+3) \to 3(+2) \to 4(+2)2(+3) \to 3(+2) \to 4(+2)$。通过这样的方式，收集到了 $7$ 颗小球。 为了收集 $14$ 颗小球，我们可以按照以下步骤进行：$2(+3) \to 3(+2) \to 1(+1) \to 4(+2) \to 5(+1)2(+3)\to 3(+2)\to 1(+1)\to 4(+2)\to 5(+1)$ 重新产生小球 $5(+1) \to 4(+2) \to 2(+3)5(+1)\to 4(+2)\to 2(+3)$。通过这样的方式，收集到了 $15$ 颗小球。 为了收集 $23$ 颗小球，我们可以按照以下步骤进行：$2(+3) \to 3(+2) \to 1(+1) \to 4(+2) \to 5(+1)2(+3)\to 3(+2)\to 1(+1)\to 4(+2)\to 5(+1)$ 重新产生小球 $5(+1) \to 4(+2) \to 2(+3) \to 3(+2) \to 1(+1)5(+1)\to 4(+2)\to 2(+3)\to 3(+2)\to 1(+1)$ 重新产生小球 $1(+1) \to 4(+2) \to 2(+3)1(+1)\to 4(+2)\to 2(+3)$。通过这样的方式，收集到了 $24$ 颗小球。

Consider the first test. In order to collect $ 5 $ pellets, the player should collect $ 3 $ pellets in the safe zone $ 1 $ (which is starting), move to zone $ 3 $ , collect $ 2 $ pellets there. In order to collect $ 8 $ pellets, the player should collect $ 3 $ pellets in the safe zone $ 1 $ , go to $ 2 $ , collect $ 1 $ pellet, go to $ 1 $ without getting pellets, go to $ 3 $ , collect $ 2 $ pellets. Now the last pellet in the world is collected, so they are respawned. The player can collect $ 2 $ pellets in the safe zone $ 3 $ and now the number of collected pellets is $ 8 $ . Consider the second test. In order to collect $ 7 $ pellets let's do the following: $ 2(+3) \rightarrow 3(+2) \rightarrow 4(+2) $ . In such a way $ 7 $ pellets were collected. In order to collect $ 14 $ pellets let's do the following: $ 2(+3) \rightarrow 3(+2) \rightarrow 1(+1) \rightarrow 4(+2) \rightarrow 5(+1) $ respawn of pellets $ 5(+1) \rightarrow 4 (+2) \rightarrow 2(+3) $ . In such a way $ 15 $ pellets were collected. In order to collect $ 23 $ pellets let's do the following: $ 2(+3) \rightarrow 3(+2) \rightarrow 1(+1) \rightarrow 4(+2) \rightarrow 5(+1) $ respawn of pellets $ 5(+1) \rightarrow 4(+2) \rightarrow 2(+3) \rightarrow 3(+2) \rightarrow 1(+1) $ respawn of pellets $ 1(+1) \rightarrow 4(+2) \rightarrow 2(+3) $ . In such a way $ 24 $ pellets were collected.