ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1952. To Kill the Dragon

Time limit: 1.0 second
Memory limit: 64 MB
A small group of brave magicians gathered together to kill the bad dragon. Since they do it every week (sometimes in several attempts), they know the dragon’s behaviour by heart and can predict all his moves with one second precision.
There are two kinds of magicians: attackers and healers. The purpose of attackers is to damage the dragon, and the purpose of healers is to heal injured magicians. Each attacker can surround the dragon with an anti-magic aura that continuously damages the dragon. Similarly, each healer can surround all magicians on the battlefield with an aura that continuously restores their health.
While a magician maintains his spell, the power of his aura (the damage or healing in a unit of time) increases linearly. But the power of the aura of each magician can not exceed some fixed value associated with the magician. While a magician does not maintain the spell, the power of his aura decreases linearly until it falls to zero. So the power of an aura can never become negative.
Auras of different magicians are independent and don’t influence each other. The total damage the dragon gets equals to the sum of damages from every attacker’s aura. Similarly, the total healing each magician gets equals to the sum of amounts of healing from every healer’s aura. Hit points of a magician can not exceed their initial value that is the same for each magician.
During the battle, the dragon uses different spells in some fixed order. The same type of spell can be used multiple times in a row.
The first spell is Fire Storm. It creates a wall of fire all over the field except for a small plot of land in the center of the storm. While a magician is located in the fire, he gets constant damage equal to the power of this spell and is not able to cast a spell. There is enough space in the center of the storm to locate all magicians without getting damage, and there they can cast spells. The center of the storm can appear in different places each time this spell is used.
The second spell is Dragon’s Breath. While the dragon uses it, all magicians in the field get constant damage equal to the power of this spell. Fortunately, there are some relatively safe locations, where magicians can cast their spells (in the other points magicians can not do this). However, such locations are too small, and at each of them, there is room for only one magician. The number of such locations always equals to the number of magicians. Similar to the Fire Storm, relatively safe locations can appear in different places each time. Since Dragon’s Breath takes much magic power, the dragon never uses it more than two times in a row.
After a while, the dragon gets tired of the battle and strikes all magicians with his tail, instantly killing them.
An attack of the dragon is either using one of his two spells or his tail strike. The first attack starts at time 0. Each subsequent attack starts at the time the previous attack is finished. At the very moment when the dragon switches two attacks, the first of them is considered to have effect.
Magicians don’t like to be fried, so each of them runs to the center of the fire storm along a straight line right after it starts. In case of Dragon’s Breath, each magician chooses one of the relatively safe locations for himself and runs straight to that location. Several magicians can run through the same point at the same time. However, it doesn’t deny the fact that each relatively safe location can be considered only for exactly one magician.
The dragon does not like to hurry, so the duration of his spells is long enough for all magicians to reach every safe location of the current spell from every safe location of the previous spell regardless of which magicians go to which safe locations. (Note however that there is no guarantee that they can get to their destinations alive.) Moreover, if the current spell is Fire Storm, then its duration is long enough not only to reach its center but also to increase the power of all attacking and healing auras to maximum value and to totally restore all magicians’ health regardless of how much health they had. Dragon’s spells can have different power but it is always strictly greater than the maximal total power of all healing auras.
If at some moment hit points of any magician fall to zero, all magicians die. Killing the dragon is slightly more complicated than killing a magician. It is necessary not only to make his hit points equal to zero but also to cast a final spell. Casting the final spell requires all magicians to gather at the center of the fire storm. Obviously, magicians must be alive to cast the final spell. The final spell can be cast instantly.
At time 0, all magicians are located at the origin, the power of every healer’s aura is equal to its maximal level, and the power of every attacker’s aura is equal to zero.


In the first line of input, you are given three nonnegative integers n, m and k: the number of attackers, the number of healers and the total number of dragon’s attacks (1 ≤ n, m ≤ 9; n + m ≤ 10; 1 ≤ k ≤ 10). In the second line, there are three integers hpm, v and hpd: initial hit points and velocity of each magician and initial hit points of the dragon (1 ≤ hpm, hpd ≤ 109; 1 ≤ v ≤ 106).
The next n lines describe attackers. On i-th of them, there are three integers dpsi, idi and ddi: the maximal power of i-th attacker’s aura, the increment of the power of his aura per unit of time while he maintains the spell, and decrement of the power of his aura per unit of time while he runs to the next safe location (1 ≤ dpsi, idi, ddi ≤ 106).
The next m lines describe healers. On i-th of them, there are three integers hpsi, ihi and dhi describing the same values that were described by numbers dpsi, idi and ddi for attackers. (1 ≤ hpsi, ihi, dhi ≤ 106).
After that, there are k blocks which describe dragon’s attacks in chronological order.
If the attack is a Fire Storm, the first line of the block contains a single word “Storm”. On the second line of the block, you are given space-separated integers d and t: the power and duration of the spell (1 ≤ d, t ≤ 106). On the third line of the block, there are two integers x and y: coordinates of the center of this storm (−1000 ≤ x, y ≤ 1000).
If the attack is a Dragon’s Breath, the first line of the block contains a single word “Breath”. On the second line of the block, you are given space-separated integers d and t: the power and duration of the spell (1 ≤ d, t ≤ 106). The next n + m lines of the block contains two integers each xi and yi: coordinates of relatively safe locations. All relatively safe locations are different.
If the attack is a Tail Strike, its description is a single word “Tail”.
It is guaranteed that among all attacks, there is exactly one Tail Strike and this attack is the last one. It is also guaranteed that there can not be more than two Dragon’s Breaths in a row.
Durations of spells are given in seconds, coordinates are in meters, velocities are in meters per second. Powers of magicians’ auras and powers of the dragon spells are given in hit points per second, the increment and the decrement of powers of auras are in hit points per square second.
Note that, although the given values are all integers, all movement, damage, healing and changes in aura powers happen continuously.


If the magicians are not able to kill the dragon, output a single line “You are not prepared”.
Otherwise, on the first line, output “No useful loot again”. On the second line, output one integer: the minimal number of attack during which the dragon can die. Attacks are numbered from 1.


1 1 2
1 5 10
1 3 2
1 1 1
7 11
0 0
No useful loot again
1 1 2
1 5 10
1 3 2
1 1 1
7 10
0 0
You are not prepared
Problem Author: Denis Dublennykh
Problem Source: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013