THỰC HÀNH

(Đề đề xuất DHBB 2017 của THPT CHUYÊN TUYÊN QUANG)

Vicky có n cuốn sách và anh ta muốn đóng một giá sách một hoặc nhiều tầng để chứa tất cả các cuốn sách này. Mỗi cuốn sách có chiều rộng w_i và chiều cao h_i. Các cuốn sách cần được bỏ vào các tầng theo thứ tự. Ví dụ như tầng thứ nhất cần bỏ các cuốn sách từ 1 đến k, tầng thứ 2 sẽ bắt đầu từ cuốn sách thứ k + 1, và cứ thế tiếp tục. Giá sách có chiều rộng là L. Chiều cao của một tầng bằng với chiều cao của cuốn sách có chiều cao lớn nhất xếp vào tầng đó, và chiều cao giá sách bằng với tổng chiều cao của các tầng (coi như các giá ngăn giữa các tầng dày không đáng kể). Hãy giúp Vicky tính chiều cao thấp nhất có thể của giá sách. Chú ý là các tầng không nhất thiết phải xếp tối đa số sách có thể.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương n và L được ghi cách nhau một dấu cách.
• n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương h_i và w_i được ghi cách nhau một dấu cách.

Dữ liệu ra:

            Một số dương duy nhất là chiều cao tối thiểu của giá sách.

Ví dụ:

Dữ liệu vào:
5 10
5 7
9 2
8 5
13 2
3 8
Dữ liệu ra:
21

Giải thích: Giá sách được làm ba tầng:

• Tầng 1 xếp quyển số 1 với chiều cao 5
• Tầng 2 xếp các quyển số 2, 3, 4 với chiều cao 13
• Tâng 3 xếp quyển số 5 với chiều cao 5

Tổng chiều cao của giá sách là 21

Giới hạn: 1 ≤ N ≤ 2000; 1 ≤ L, h_i ≤ 10⁹; 1 ≤ w_i ≤ L.