Each night, deep in the Dreamyards, a hungry Munna prepares to go on a journey to feast upon the tasty dreams of nearby Pokémon. There are $$$D$$$ $$$(1 \le D \le 10^4)$$$ dreams in total, dream $$$1$$$ to dream $$$D$$$, and each dream has some specific satisfaction $$$D_i$$$ $$$(1 \le D_i \le 10^9)$$$ that Munna gets from eating it. Munna's hunger varies night by night – on any of the $$$H$$$ $$$(1 \le H \le 10^5)$$$ given nights, Munna can eat dreams with satisfaction values whose sum does not exceed its hunger for that night $$$H_i$$$ $$$(0 \le H_i \le 10^{13})$$$.
Munna has a list of $$$P$$$ $$$(0 \le P \lt D)$$$ unique pairs of dreams. Each pair $$$a_i$$$ and $$$b_i$$$ informs Munna that dream $$$b_i$$$ can only be eaten directly after dream $$$a_i$$$. It is guaranteed that there are no cycles – i.e. there is no set of dreams that all depend on each other. Each dream has at most one prerequisite dream, so all values of $$$b_i$$$ are unique.
This particular Munna loves to eat dreams along a path. A path of dreams is a list of dreams to eat where:
- The first dream has no prerequisite dreams.
- For each consecutive pair of dreams $$$d_i$$$ and $$$d_{i+1}$$$ in the path, that pair exists in the list of $$$P$$$ edges.
Each night, Munna has some amount of hunger $$$H_i$$$. For each night, find the path with the highest satisfaction sum that is less than or equal to $$$H_i$$$. If there are multiple such paths, find the path with the minimum number of dreams.
Note: This problem requires the use of 64-bit integers. In C/C++ use long long and in Java use long. Not a concern for Python or Javascript.
The first line consists of three integers $$$D$$$, $$$P$$$, and $$$H$$$: the number of dreams, pairs, and nights.
The second line consists of $$$D$$$ space-separated integers $$$(1 \le D \le 10^4)$$$: the satisfaction values of each dream $$$(1 \le D_i \le 10^9)$$$.
Following these two lines are $$$P$$$ $$$(0 \le P \lt D)$$$ lines, where each line is a pair of space-separated integers $$$a_i$$$ and $$$b_i$$$ $$$(1 \le a_i, b_i \le D, a_i \neq b_i)$$$: dream $$$b_i$$$ can only be eaten directly after dream $$$a_i$$$.
The last line has $$$H$$$ space-separated integers $$$(1 \le H \le 10^5)$$$: Munna's hunger on each night $$$(0 \le H_i \le 10^{13})$$$.
Output $$$H$$$ lines, with line $$$i$$$ containing two space-separated integers: the satisfaction and the number of dreams for the path with highest satisfaction sum less than or equal to $$$H_i$$$. If multiple paths result in the same satisfaction, output the minimum number of dreams of the paths.
7 4 63 1 5 4 15 66 107 52 41 21 34 10 9 30 1 100
4 2 10 1 8 2 25 2 0 0 66 1
On night $$$1$$$, Munna eats dreams $$$1 \rightarrow 2$$$.
On night $$$2$$$, Munna eats dream $$$7$$$.
On night $$$3$$$, Munna can eat $$$1 \rightarrow 2 \rightarrow 4$$$ or $$$1 \rightarrow 3$$$. Munna chooses the shorter path $$$1 \rightarrow 3$$$.
