Monster Slayer Strategy Optimization

You are playing a monster‐slaying game on a map. The map has \(n\) cities connected by \(m\) undirected roads such that all cities are reachable from one another. Each city \(i\) has a monster with health \(a_i\). Initially, you carry \(k\) weapons. The \(i\)th weapon has a durability of \(b_i\) and the weapons must be used in the given order: you always use the first available weapon. When fighting a monster, if the current weapon's durability is at least the monster's remaining health, you defeat the monster and the weapon's durability decreases by the monster's health. Otherwise, if the current weapon's durability is less than the monster's health, you must immediately discard it and switch to the next weapon. If you run out of weapons, you lose.

Furthermore, there are \(q\) items scattered in different cities. The \(i\)th item is located in city \(c_i\) and has a property value \(d_i\). After you defeat the monster in a city, if that city contains an item, you obtain it. An item can be used in a future battle before attacking a monster to reduce the monster's health by \(d_i\) (but not below \(0\)), and each monster can have at most one item applied. Each item may be used at most once, and you do not have to use an item immediately upon obtaining it.

Your task is to determine whether you can defeat all monsters. If you can, you must find an optimal strategy that minimizes the number \(x\) of weapons used. If there are multiple strategies that use the same minimum number of weapons, choose the one in which the remaining durability \(y\) of the last used weapon is maximized. Output \(x\) and \(y\). If it is impossible to defeat all monsters, output the string FAIL.

Note on optimal strategy: Since the map is connected you can choose the order in which you visit the cities. An optimal strategy involves first choosing a starting city (preferably one without an item if possible, because when every city has an item you lose one potential item) so that you can collect items from other cities before facing the tougher monsters. Then, assign items to monsters in order to reduce their effective health. In particular, if you have \(r\) available items (where \(r=q\) if there is at least one city without an item, or \(r=n-1\) if every city contains an item), you may assign items to the \(r\) monsters with the highest initial health. For a monster with health \(a\) and an item with value \(d\), its effective health becomes \(\max(0, a-d)\). After computing the effective health of all monsters, you may fight them in ascending order of effective health. When fighting, you use the weapons in their given order. For each monster, if the current weapon's remaining durability is not less than the monster's effective health, you can defeat it and subtract that amount from the weapon's durability; otherwise, you discard the current weapon and move to the next one. If at any point you run out of weapons, the answer is FAIL.

inputFormat

The first line contains four integers \(n\), \(m\), \(k\) and \(q\) -- the number of cities, roads, weapons, and items respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the health of the monster in each city.

The following \(m\) lines each contain two integers \(u\) and \(v\), denoting an undirected road between cities \(u\) and \(v\). It is guaranteed that the graph is connected.

The next line contains \(k\) integers \(b_1, b_2, \dots, b_k\) representing the durability of the weapons in the order you must use them.

The next \(q\) lines each contain two integers \(c_i\) and \(d_i\), indicating that an item with property value \(d_i\) is located in city \(c_i\). Each city contains at most one item.

outputFormat

If it is possible to defeat all monsters, output two integers \(x\) and \(y\) on one line, where \(x\) is the number of weapons used and \(y\) is the remaining durability of the last used weapon based on the optimal strategy. Otherwise, output the string FAIL (without quotes).

sample

3 2 3 1
5 10 3
1 2
2 3
7 10 6
2 6

2 5