Vì đã thua Nhân và Lượng ở trận đấu cào cào , Hưng đã biết mình cần phải học thêm nhiều điều. Chính vì vậy, với quyền năng của mình Hưng đã dựng lên 1 thư viện để học tập. Thư viện có N quyển sách . Mỗi ngày Hưng đọc một số quyển sách trong số N quyển này và vì sở hữu trí não siêu phàm chỉ cần đọc 1 lần là nhớ cả đời nên Hưng sẽ không đọc quyển sách nào quá 1 lần. Chính vì vậy,Hưng đã lên kế hoạch để có thể đọc được nhiều kiến thức nhất.Nhưng vì là người đãng trí , Hưng quyết định sẽ đọc các cuốn sách theo thứ tự tăng dần từ cuốn 1 đến cuốn N. Biết được Hưng đang Nâng cao trình độ để báo thù mình. Nhân và Lượng đã lên kế hoạch để phù phép sách của Hưng . Từ khi đó mỗi quyển sách của Hưng lại có thêm chỉ số buồn chán. Điều đó khiến Hưng không thể đọc các cuốn sách liên tục vì có thể sự buồn chán đó có thể vượt qua giới hạn K của Hưng nhưng sau một ngày thì niềm hứng thú của Hưng sẽ trở lại. Quy tắc tính kiến thức của Hưng cũng rất độc lạ khi số kiến thức anh đọc được sẽ được tính bằng giá trị kiến thức lớn nhất của những cuốn sách anh đọc được ngày hôm đó.Nhằm đánh lừa Lượng và Nhân, Hưng muốn nhận được ít kiến thức nhất vì anh nghĩ như thế sẽ khiến kẻ địch buông lỏng cảnh giác nên Hưng đã nhờ Nhật Minh soạn ra các quyển sách mà ngày hôm đó Hưng đọc sao cho không vượt quá giới hạn của Hưng mà sau khi đọc hết toàn bộ N quyển sách,tổng toàn bộ kiến thức mà Hưng nhận được phải là bé nhất.Nhật Minh loay hoay mãi mà không nghĩ ra cách còn Hưng thì quá Lười . Các bạn hãy giúp nhé !

Lưu ý: Hưng sẽ đọc các cuốn sách liên tiếp từ 1 đến N.

Dữ liệu

Dòng đầu tiên là 2 số nguyên dương N,K là số lượng cuốn sách và giới hạn của Hưng. N dòng tiếp theo, dòng thứ i chứa 2 số nguyên dương a[i] và b[i] là kiến thức của cuốn sách thứ i và độ buồn chán khi đọc nó.

Kết quả

Gồm một dòng duy nhất chứa số kiến thức nhỏ nhất mà Hưng có thể đạt được

Ràng Buộc

N<=1024,K<=1000000000; * Mọi i từ 1 đến N: a[i]<=1000000000,b[i]<=k;

Sample input

5 10
5 7
9 2
8 5
13 2
3 8

Sample output

21

Giải thích

• Ngày đầu tiên Hưng đọc quyển 1
• Ngày thứ 2 Hưng đọc quyển 2,3,4
• Ngày thứ 3 Hưng đọc quyển số 5