Bờm vừa tìm được một mỏ vàng cực kì hiếm trong một hang động. Mỏ vàng này bao gồm ~N~ cục vàng. Cục vàng thứ ~i~ sẽ cần ~A_i~ giây để đào lên, và giá trị của cục vàng là ~B_i~. Tuy nhiên, do thời gian có hạn, Bờm chỉ có thế đào được một số cục vàng trong thời gian ~T~ giới hạn. Bờm có thể đào các cục vàng theo quy tắc sau:

• Bờm bắt đầu đào vàng tại thời điểm ~0~.
• Bờm có thể đào các cục vàng theo bất kì thứ tự nào.
• Tại mỗi thời điểm, Bờm chỉ có thể đào một cục vàng.
• Trong khi đang đào vàng, Bờm không được chuyển qua đào cục vàng khác cho tới khi đào xong cục vàng hiện tại.
• Sau khi đào xong cục vàng hiện tại, Bờm có thể ngay lập tức chuyển qua đào cục vàng khác mà không tốn thêm thời gian nào.
• Sau thời điểm ~T - 0.5~, Bờm không được chuyển qua đào cục vàng mới, nhưng nếu Bờm vẫn đang đào một cục vàng hiện tại, thì Bờm sẽ đào cho xong rồi mới kết thúc quá trình đào vàng.

Thời gian gấp rút như thế, nhưng Bờm vẫn chưa quyết định được nên đào các cục vàng theo thứ tự như thế nào. Bạn hãy giúp Bờm xác định cách đào vàng để được tổng giá trị những cục vàng đào được là nhiều nhất nhé.

Dữ liệu

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~T~ ~(1≤ N,T ≤3000)~ – Số lượng cục vàng và thời gian ~T~ để Bờm có thể đào vàng.

• ~N~ dòng tiếp theo, dòng thứ ~i~ bao gồm hai số nguyên ~A_i~ và ~B_i~ ~(1≤ A_i,B_i ≤3000)~ – Thời gian để đào và giá trị của cục vàng thứ ~i~.

  Kết quả

• In ra một số nguyên duy nhất là tổng giá trị vàng đào được nhiều nhất.

Ví dụ

Sample Input 1

2 50
20 10
100 20

Sample Output 1

30

Sample Input 2

3 70
30 10
30 20
30 30

Sample Output 2

60

Sample Input 3

3 60
30 10
30 20
30 30

Sample Output 3

50

Giải thích

• Ở ví dụ 1, Bờm đào cục vàng thứ nhất, sau đó đào cục vàng thứ hai, giá trị vàng thu được là tối đa. Lưu ý rằng nếu Bờm đào cục vàng thứ hai trước, thì Bờm không thể đào cục vàng thứ nhất, do đã vượt quá thời điểm ~T - 0.5~.
• Ở ví dụ 2, Bờm có thể đào được các cục vàng theo thứ tự bất kì, giá trị vàng thu được là ~60~, nhiều nhất có thể.
• Ở ví dụ 3, Bờm đào cục vàng thứ hai và thứ ba. Do đã vượt quá thời điểm ~T - 0.5~, nên Bờm kết thúc quá trình đào vàng và giá trị vàng tổng là ~50~, nhiều nhất có thể.

Nguồn: Free Contest 124