Giá sách (Khó)

Có $N$ quyển sách cần xếp theo thứ tự lên các kệ, mỗi kệ có chiều rộng tối đa $L$. Chiều cao của một kệ bằng chiều cao quyển sách cao nhất trên kệ đó. Tối thiểu hóa tổng chiều cao.

Dữ liệu vào

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

Dữ liệu ra

Một số nguyên — tổng chiều cao tối thiểu.

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ụ