
ZOJ Problem Set  3369
Saving princesses is always a hard work. Ivan D'Ourack is planning to save the princess locked in the tower. However, n dangerous monsters are guarding the road from the city where Ivan lives to the tower where the princess is locked. Fortunately Ivan is a warrior and a magician. Thus he can defeat monsters in a fight, and enchant them to pass unnoticed. Initially Ivan has h health points, strength s, spell power p and m mana points. To defeat ith monster in a fight, he must have strength at least s_{i}, and he loses max(2s_{i}  s, 0) health points in a fight. If the number of health points becomes 0 or less, Ivan dies. After defeating a monster Ivan's strength increases by 1. To enchant ith monster Ivan must have spell power at least p_{i} and he spends m_{i} mana points to do it. If Ivan does not have m_{i} mana points, he cannot enchant the monster. After enchanting the monster Ivan's spell power increases by 1. Find out, whether Ivan can save princess, and if he can how to do it. InputThe first line of the input file contains n, h, s, p and m (1 ≤ n ≤ 50, 1 ≤ h ≤ 50, 0 ≤ s, p, m ≤ 50). The following n lines contain three integer numbers each  s_{i}, p_{i}, and m_{i} (1 ≤ s_{i}, p_{i}, m_{i} ≤ 50). There are multiple cases. Process to the end of file. OutputIf Ivan cannot save princess, output "UNLUCKY". In the other case output n characters, the ith character must be 'D' if Ivan must defeat the ithe monster, or 'E' if he must enchant it. Sample Input3 12 5 5 6 5 5 2 6 5 2 6 7 3 3 11 5 5 6 5 5 2 6 5 2 6 7 3 Sample OutputDED UNLUCKY Author: Andrew Stankevich Source: Andrew Stankevich's Contest #11 