#P1346I. Pac-Man 2.0
-
ID: 5336
Type: RemoteJudge
3000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Pac-Man 2.0
No submission language available for this problem.
Description
Polycarp is developing a new version of an old video game "Pac-Man". Though he really enjoyed playing the original game, he didn't like some aspects of it, so he decided to alter the rules a bit.
In Polycarp's version, you play as Pac-Man and you have to collect pellets scattered over the game world while avoiding dangerous ghosts (no difference from the original yet). Polycarp didn't like the fact that there was no escape from the ghosts in the original, so, in his version, the game world is divided into $n$ safe zones with $m$ one-directional pathways between them — and it is guaranteed that Pac-Man can reach any safe zone from any other. Since safe zones are safe, the ghosts cannot attack Pac-Man while it is there, it is in danger only while traversing the pathways. Pac-Man starts the game in the safe zone $s$.
All pellets are scattered over the safe zones; initially, the $i$-th safe zone contains $a_i$ pellets (and if Pac-Man is in a safe zone, it may freely collect all the pellets in it). The pellets disappear after being collected, but after the last pellet in the game world is collected, new pellets spawn in the safe zones in the same quantity as before ($a_i$ new pellets spawn in the $i$-th zone). The pellets can be respawned any number of times, so the game is essentially infinite.
Polycarp has already determined the structure of the game world and the number of pellets in each safe zone. Now he is trying to find out if the game is difficult enough. There are $q$ goals in the game, the $i$-th goal is to collect at least $C_i$ pellets from the beginning of the game. Polycarp denotes the difficulty of the $i$-th goal as the minimum number of times the player has to traverse a one-directional pathway in order to collect $C_i$ pellets (since only traversing a pathway puts Pac-Man in danger). If some pathway is traversed multiple times while Pac-Man is collecting the pellets, it is included in the answer the same number of times.
Help Polycarp to calculate the difficulty of each goal!
The first line contains four integers $n$, $m$, $q$ and $s$ ($2 \le n \le 15$; $n \le m \le n(n-1)$; $1 \le q \le 5000$; $1 \le s \le n$) — the number of safe zones, the number of pathways, the number of goals and the index of the starting safe zone, respectively.
The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the initial number of pellets in the $i$-th safe zone (and the number of pellets that spawn in the $i$-th safe zone when the last pellet in the world is collected).
Then $m$ lines follow, each line contains two integers $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$; $v_i \ne u_i$) denoting a one-directional pathway from the safe zone $v_i$ to the safe zone $u_i$. Each ordered pair $(v_i, u_i)$ appears in this section at most once (there are no multiple pathways from $v_i$ to $u_i$), and it is possible to reach every safe zone from every other safe zone using these pathways.
The last line contains $q$ integers $C_1$, $C_2$, ..., $C_q$ ($1 \le C_i \le 10^{15}$), where $C_i$ is the minimum number of pellets the player has to collect in order to fulfil the $i$-th goal.
For each goal $i$, print one integer — its difficulty (the minimum number of times the player has to traverse along some pathway in order to collect at least $C_i$ pellets).
Input
The first line contains four integers $n$, $m$, $q$ and $s$ ($2 \le n \le 15$; $n \le m \le n(n-1)$; $1 \le q \le 5000$; $1 \le s \le n$) — the number of safe zones, the number of pathways, the number of goals and the index of the starting safe zone, respectively.
The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the initial number of pellets in the $i$-th safe zone (and the number of pellets that spawn in the $i$-th safe zone when the last pellet in the world is collected).
Then $m$ lines follow, each line contains two integers $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$; $v_i \ne u_i$) denoting a one-directional pathway from the safe zone $v_i$ to the safe zone $u_i$. Each ordered pair $(v_i, u_i)$ appears in this section at most once (there are no multiple pathways from $v_i$ to $u_i$), and it is possible to reach every safe zone from every other safe zone using these pathways.
The last line contains $q$ integers $C_1$, $C_2$, ..., $C_q$ ($1 \le C_i \le 10^{15}$), where $C_i$ is the minimum number of pellets the player has to collect in order to fulfil the $i$-th goal.
Output
For each goal $i$, print one integer — its difficulty (the minimum number of times the player has to traverse along some pathway in order to collect at least $C_i$ pellets).
Samples
3 4 2 1
3 1 2
1 2
2 1
1 3
3 1
5 8
1
3
5 7 4 2
1 3 2 2 1
2 3
4 2
3 4
3 1
1 4
5 4
4 5
7 14 23 27
2
6
10
13
4 4 3 3
2 3 1 4
3 4
4 1
1 2
2 3
13 42 1337
3
13
401
Note
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.