Hide

Problem J
Grand Combat Delusion: The Movie

Languages en is
They decide to watch another film, even though it’s getting late. The film they choose is Grand Combat Delusion: The Movie, a film adaptation of the popular video game by the same name. The character in the movie needs to gather better equipment to beat their foe, similar to the video game. A new character to the franchise, Anna, points out that it may be a good idea to use more than one piece of equipment. You are again tasked with finding the cheapest way to defeat all the enemies with this new idea in mind.

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

Please log in to submit a solution to this problem

Log in