Word Clouds Revisited

Source: Kattis

Version: Phuoc Hung OJ Extended

Problem Statement

This package preserves the original task mechanism. 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.

Subtasks

• Subtask 1 — 20 points: small data.
• Subtask 2 — 30 points: medium data.
• Subtask 3 — 50 points: full PHOJ package limits.

Examples

Input

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

Output

99

Explanation

The output follows directly from the rules above.