P11400 [Code+#8 初赛] 打怪游戏

搬运自 [Code+ #8 初赛](https://gitlink.org.cn/thusaa/codeplus8pre)。

你正在玩一个打怪的小游戏。游戏在一张地图上进行，你的任务是手持武器，消灭地图上的所有怪物。 地图上有 $n$ 座城市，$m$ 条无向道路相连这些城市，使得所有的城市都能通过道路直接或间接相连。每个城市上有一个怪物，第 $i$ 座城市的怪物血量是 $a_i$ 。 最初，你有 $k$ 把武器，第 $i$ 把武器的耐久值为 $b_i$ 。 你可以任选一个城市出发，沿道路行进。每当你第一次到达某个城市时，你需要与那里的怪物作战。作战规则为：你按照编号顺序使用手里的第一把武器，如果武器当前的耐久不低于怪物的血量，你就可以打死怪物，但武器会减少相当于怪物血量的耐久值；如果当前的武器耐久低于怪物血量，你便不能用这把武器打怪，需要立刻将这把武器丢弃并换下一把；如果你没有武器可换了，你就输掉了游戏。 同时，地图上有 $q$ 个道具，分布在不同的城市，第 $i$ 个道具位于城市 $c_i$，其属性值为 $d_i$。每当你打死一个城市的怪物之后，如果这个城市有道具，你获得之。道具的作用是当你打怪的时候，你可以事先对怪使用一个道具使得怪的血量减少 $d_i$，减少到 $0$ 为止。每个道具最多只能被使用一次，每个怪只能被使用至多一个道具，注意道具并不需要获得后立刻使用。 请问：你能否战胜所有的怪？如果能，请求出最优策略（即使用的武器数量 $x$ 最少，如有并列则最后一把使用的武器的剩余耐久 $y$ 最高），并输出 $x$ 和 $y$；如果不能取胜，只需输出一个字符串 `FAIL`。

第 $1$ 行，$4$ 个非负整数 $n,m,k,q$。 接下来 $m$ 行，每行 $2$ 个正整数 $u_i,v_i$，表示一条连接城市 $u_i$ 与 $v_i$ 的道路。 接下来 $1$ 行， $n$ 个正整数 $a_i$，表示怪物的血量。 接下来 $1$ 行，$k$ 个正整数 $b_i$，表示武器的初始耐久值。 接下来 $q$ 行，每行 $2$ 个正整数 $c_i,d_i$，描述一个道具。

输出共一行，如果存在获胜策略，输出 $2$ 个正整数 $x,y$，表示最优策略下使用了前 $x$ 把武器，最后一把使用的武器的剩余耐久是 $y$；如果不能取胜，输出一个字符串 `FAIL`。

**【样例 #1 解释】** 你的最优策略是先打城市 $3$ 的怪物。虽然你会直接丢弃武器 $1$，但你接下来可以凭借道具在不消耗耐久的前提下战胜城市 $2$ 和城市 $1$ 的怪物。如果选择先打城市 $1$ 的怪物，最后武器 $2$ 将只剩 $0$ 点耐久。 **【样例 #2 解释】** 因为你不能把两个道具都对城市 $3$ 的怪物使用，因此你无论如何也打不赢它。 **【数据范围】** 对于全部数据，$1\leq n \leq 18$，$n-1\leq m \leq n(n-1)/2$，$1\leq k \leq n$，$0\leq q \leq min(n,8)$，$1 \leq a_i,b_i \leq 10^9$，$1 \leq c_i \leq n$，$1 \leq d_i \leq 10^9$，$1 \leq u_i,v_i \leq n$，$u_i \neq v_i$。保证所有 $c_i$ 互不相同，保证任何一对城市之间最多只有一条道路直接相连，且保证给出的图联通。