1299 - Baijingyuan’s celebration

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 176

Solved: 41

Description

To celebrate the 8th anniversary of establishment of Baijingyuan Dining Hall, The HUST Logistic Services prepare a large number of point ticket repayment teachers and students. As a fans of Baijingyuan, Gaewah of course won’t miss the chance.
Each point ticket has a point and a value. For every user, if this is the i-th ticket you get, the ticket will be add a serial number i.
Then if you collect some continuous serial number tickets, and the sum of the ticket’s point is equal or more than M, you can get the maximum value of these tickets’ value.
Gaewah collect N tickets numbered 1,2,……,N. He want to know the maximum total value he can get.
Input
The first line you can get a number t indicate the number of test case.
For each test case:
The first line have 2 integers N and M indicate the number of ticket Gaewah collect and the minimum point M to exchange the value.(1<=N,M<=50000)
Then N lines. Each line has 2 integers indicate the i-th tickets’ point and value.(point and value will ranged in [0..2^31-1])
Output
For each case just output a integer indicate the maximum value Gaewah can get.
sample input
1
4 4
1 5
2 4
1 6
10 10
sample output
16
hint
source
Hust Monthly 09.08.21/Zehua HONG
© 2015 HUST ACMICPC TEAM. All Right Reserved.