bee 1487 - Six Flags

Six Flags Fiesta Texas is one of the biggest amusement parks of the world and it is located in San Antonio. Since the ACM-ICPC World Finals of 2006 are going to be held there, three friends started to plan which of the famous rides of the park they would go to in case their team was classified to the finals.

They decided to establish grades for each one of the rides according to their desire to go there. For example, the "Superman Krypton Coaster" roller coaster (which goes through 800m of twists, turns and spirals over the speed of 100km/h) received the highest score between the friends.

The problem entails on the impossibility of visiting every ride on the park in only one day. Thus, the friends investigated, for each attraction, how long did the ride last (and how much time in the line till you get to it...). Your task is to find, giving the time available by the three pals, a collection (there may be repetitions) of rides that amounts to the highest score in the given time.

Input

The input contains several test cases. The first line of a test case contains two integers 0 ≤ N ≤ 100 e 0 ≤ T ≤ 600, in which N is the number of rides that the friends would like to go to and T is the time (in minutes) available for this. The next N lines contain two integers 0 ≤ D ≤ 600 e 0 ≤ P ≤ 100 (in each line). The first one, D, represents the the duration of the ride (time spent in the line and moving from one ride to another are included). P represents the score given by the friends. The end of the input is indicated then the value of N = 0.

Output

For each of the test case in the input, your program must print a line using an identifier Instancia H, in which H is an ascending and sequential integer starting from 1. The following line must contain the total score of the collection determined by your program. Regarding which rides of the collection would be chosen, the friends decided they would ask you in the future, since they didn't want people to know and decide to use it. A blank line must be printed after each test case.

Sample Input	Sample Output
5 60 10 30 20 32 5 4 50 90 22 45 5 60 10 10 20 32 5 4 50 90 22 45 0 0	Instancia 1 180 Instancia 2 104