Plants VS Zombies

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2831
64-bit integer IO format: %I64d      Java class name: Main
Special Judge

Description

Plants VS Zombies is a popular game in the TJU ACM Team now. However, RoBa is not very good at this game, so he wants you to write a program to help him.

We take a simplified version of this game. There are N rows in your backyard, and there are N zombies want to walk through your yard to eat your brain, and exactly one zombie in each row. The only method to defense the zombies is to plant “peashooter” on the other side of the yard. However, you need T seconds to plant one peashooter. Once the peashooter is planted, it will begin to shoot at the zombies in its row. The zombies have different speed Vi and defense Di, which means that, the zombie in the i-th row need Vi second the walk though the yard, and the i-th zombie will be killed after Di second of shooting. Please note you can only plant one peashooter in each row.

Unfortunately, in some cases, for the zombies are too fast and/or too strong and/or your planting is too slow, you cannot kill all the zombies in time, so the zombies will eat your brains.

Input

There are several test cases in the input. The first line of each test case contains two integers N (1 <= N <= 100) and T, indicating the number of rows and the time for planting one peashooter. Then N lines follow, each of which contains two integers Vi and Di.

Output

Output one line for each test case. If you can kill all the zombies, output N numbers separated by a space, that is, a permutation of 1,2,…N, indicating the order of your planting. If you cannot defend your yard, output “The zombies eat your brains!” in one line.

Sample Input

3 10
20 10
40 10
30 10
3 10
20 10
40 11
30 10

Sample Output

1 3 2
The zombies eat your brains!

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .