Khi không vắt sữa bò, xếp các kiện cỏ khô, cho đàn bò xếp hàng hay dựng hàng rào, Farmer John thích ngồi xuống đọc một cuốn sách hay. Qua nhiều năm, ông đã sưu tầm được \(N\) cuốn sách (\(1 \le N \le 2\,000\)) và muốn đóng một bộ giá sách mới để chứa tất cả chúng.

Mỗi cuốn sách \(i\) có chiều rộng \(W(i)\) và chiều cao \(H(i)\). Các cuốn sách phải được xếp lên các tầng giá theo đúng thứ tự; chẳng hạn, tầng đầu tiên phải chứa các cuốn từ 1 đến \(k\) với một giá trị \(k\) nào đó, tầng thứ hai phải bắt đầu bằng cuốn \(k+1\), và cứ tiếp tục như vậy. Tổng chiều rộng trên mỗi tầng giá không được vượt quá \(L\) (\(1 \le L \le 1\,000\,000\,000\)). Chiều cao của một tầng giá bằng chiều cao của cuốn sách cao nhất trên tầng đó, còn chiều cao của toàn bộ bộ giá sách bằng tổng chiều cao của tất cả các tầng vì chúng được xếp chồng theo phương thẳng đứng.

Hãy giúp FJ tính chiều cao nhỏ nhất có thể của toàn bộ bộ giá sách.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(L\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa hai số nguyên \(H(i)\) và \(W(i)\), cách nhau bởi dấu cách (\(1 \le H(i) \le 1\,000\,000\); \(1 \le W(i) \le L\)).

Dữ liệu ra

• Dòng 1 chứa tổng chiều cao nhỏ nhất có thể của bộ giá sách.

Ví dụ

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

21

Nguồn

USACO 2012 US Open, Silver Division — Bookshelf (Silver)

Tác giả: Neal Wu / Traditional, 2012.