Đám mây từ tối ưu (Word Clouds Revisited)

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ hộp từ phải đặt theo đúng thứ tự vào các hàng. Mỗi hộp có chiều rộng $w_i$ và chiều cao $h_i$. Tổng chiều rộng của một hàng không được vượt quá $C$; chiều cao hàng là chiều cao lớn nhất của hộp trong hàng. Hãy chia thành các hàng liên tiếp để tổng chiều cao nhỏ nhất.

Input

Dòng đầu chứa $N,C$. Mỗi trong $N$ dòng sau chứa $w_i,h_i$.

Output

In chiều cao tối thiểu.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

6 260
65 23
38 11
135 48
97 43
95 28
130 23

Output

99

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.