Giá sách (Khó)

Có $N$ quyển sách cần xếp lên các kệ. Sách phải được xếp đúng theo thứ tự đã cho: mỗi kệ chứa một đoạn liên tiếp các quyển sách, kệ thứ nhất chứa các quyển đầu tiên, kệ thứ hai chứa đoạn tiếp theo, và cứ như vậy.

Quyển sách thứ $i$ có chiều cao $H_i$ và chiều rộng $W_i$. Tổng chiều rộng các quyển sách trên cùng một kệ không được vượt quá $L$. Chiều cao của một kệ bằng chiều cao của quyển sách cao nhất trên kệ đó.

Hãy tìm cách chia sao cho tổng chiều cao của tất cả các kệ là nhỏ nhất.

Dữ liệu vào

• Dòng $1$: hai số nguyên $N$ và $L$.
• $N$ dòng tiếp theo: dòng thứ $i$ chứa hai số nguyên $H_i$ và $W_i$, là chiều cao và chiều rộng của quyển sách thứ $i$.

Dữ liệu ra

Một số nguyên duy nhất: tổng chiều cao nhỏ nhất của các kệ.

Ràng buộc

• $1\le N\le 100000$
• $1\le L\le {10}^9$
• $1\le H_i\le {10}^6$
• $1\le W_i\le L$

Ví dụ