Problem J
Grand Combat Delusion: The Movie
Languages
en
is
The battles are the same as in the Grand Combat Delusion video game. Matt and his crew always have the first move. They attack the enemy and they win if it dies. Otherwise, the enemy does one point of damage to Matt and the process repeats. If Matt and the crew defeat the enemy they move onto the next one. As before, having equipment that costs $c$ increases their damage by $c$. Some equipment is cursed and costs negative money (Matt and his crew get paid to use this equipment). This equipment lowers their damage by its cost.
To add to these rules is the eccentric shopkeeper. He doesn’t like to rearrange his goods, so he will only sell you a contiguous subsequence of his wares. So if Matt and his crew want to buy two pieces of equipment, then they are forced to buy all the equipment between them. They are however also allowed to buy nothing.
Input
The first line includes two space separated integers, $n$ and $m$, with $1 \leq n, m \leq 10^5$. This denotes that there are $n$ items for sale and $m$ enemies to defeat. The next line includes two space separated integers, $h$ and $d$, with $1 \leq h, d \leq 10^5$. This denotes that Matt and his crew have $h$ initial health and do $d$ base damage. The next line includes $n$ space separated integers $c_1, \cdots c_ n$, with $-10^9 \leq c_ i \leq 10^9$. Here $c_ i$ is the price of the $i$-th equipment for sale and the equipment is listed in the order they are in the store. Finally there is one line containing $m$ space separated integers $h_1, \dots , h_ m$ with $1 \leq h_ i \leq 10^9$. Here $h_ i$ is the health of the $i$-th enemy. The enemies are list in the order they must be fought.
Output
If Matt and his crew win regardless of the equipment chosen print ‘Of audvelt!’. If they can’t, whatever they chose to buy, ‘Of erfitt!’. Otherwise print ‘x er matulegt’ where $x$ is total cost of the cheapest set of equipment that allows them to win.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 5 6 1 -1 1 9 9 9 |
Of audvelt! |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 5 2 1 -1 1 9 9 9 |
Of erfitt! |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 1 1 9 -9 4 -3 2 -4 1 |
-8 er matulegt |
