#477. DPKESACH – Giá sách

Vicky có cuốn sách và anh ta muốn đóng một giá sách 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 và chiều cao . 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ừ đến , tầng thứ sẽ bắt đầu từ cuốn sách thứ , và cứ thế tiếp tục. Giá sách có chiều rộng 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 và được ghi cách nhau một dấu cách.
• dòng tiếp theo, dòng thứ chứa hai số nguyên dương và đượ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 xếp quyển số với chiều cao
• Tầng xếp các quyển số với chiều cao
• Tâng xếp quyển số với chiều cao

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

Giới hạn:

• .