Tý có \(N\) cuốn sách cần xếp lên kệ theo thứ tự. Cuốn i dày w_i, cao h_i. Mỗi tầng chứa một số cuốn liên tiếp với tổng độ dày không quá \(W\). Chiều cao tầng bằng chiều cao lớn nhất của các cuốn trong tầng. Tổng chiều cao kệ là tổng chiều cao các tầng.

Hãy xếp sao cho tổng chiều cao nhỏ nhất.

Dữ liệu vào

• Dòng đầu gồm \(N, W\) (\(1 \le N \le 10^5, 1 \le W \le 10^9\)).
• \(N\) dòng sau, mỗi dòng \(h_i, w_i\) (\(1 \le h_i \le 10^6, 1 \le w_i \le W\)).

Kết quả ra

• In ra tổng chiều cao nhỏ nhất.

Ví dụ

Input

5 10
5 7
3 2
4 3
6 5
2 1

Output

12

Subtask