“Fortinbras: This quarry cries on havoc. O proud death, What feast is toward in thine eternal cell, That thou so many princes at a shot So bloodily hast struck” (Shakespeare, 5.2.394-397)

Fortinbras Jr, prince of Norway, has arrived in Denmark, planning to gain land for his country. Upon arrival, he observes the dead bodies of Hamlet and his family. This observation is the culmination of revenge within Hamlet. His reckless actions negatively impacting those around him have finally caught up with him. The murder of Polonius enrages his son, Laertes, down his own path of revenge. Laertes chooses to poison Hamlet under the precedent of a duel. Hamlet’s mother is caught up in this, drinking poison meant for Hamlet. Hamlet realizes all this and poisons Claudius and Laertes, creating the death Fortinbras refers to.

This unstable path of revenge Hamlet forges changes Hamlet. He becomes more illogical as his obsession with revenge consumes him. This tension within the book adds suspense and conflict through the characters, hooking the reader to the play. Once the tension is released, it projects a feeling of relief within the audience. This relaxation of conflict leaves the audience on a good note, closing the play. The theme of revenge within Hamlet constructs the story as intriguing and memorable for future generations.

Taking the place of King Claudius, Fortinbras Jr is now the new king of Denmark. With his new position, his first important task is to oversee the dead buried. Your job is to transport these people to the graveyard. Fortinbras has ordered you to prioritize people who have the highest value (least amount of sins) to carry first, as Horatio has informed him. Since some people are heavier than others, you can only lift a total of ~W~ kilograms on one trip. There will be ~N~ people who have a value of ~s~ and weigh ~w~ kilograms. Output the max value for your first trip.

Python users recommended to use PyPy3

Input specifications

The first line contains Integer ~N~, ~(1 \le N \le 150)~, representing the number of dead people to be transported, followed by integer ~W~, ~(1 \le W \le 10^5)~, the total weight you can carry The next ~N~ lines contain integer ~s~, ~(1 \le s \le 10^9)~, the value of the person, and integer ~w~, ~(1 \le w \le W)~, the weight of that person.

Output Specifications

Output the max value from people carried on your first trip to the graveyard

Sample input 1

5 60
5 30
4 40
2 60
1 10
5 5

Sample output 1

11

Sample input 1 explanation

Carry the bodies weighing 30kg with a value of 5, 10kg with a value of 1, and 5kg with a value of 5. The total possible value is 5 + 1 + 5 = 11.