Trang trại gà của nhà Bé Bo có ~n~ con gà siêu trứng đánh số từ ~1~ đến ~n~. Con gà ~i~ ~(1 \le i \le n)~ đẻ quả trứng đầu tiên ở giây ~p_i~, sau đó cứ ~t_i~ giây tiếp theo sẽ đẻ thêm một quả trứng.

Yêu cầu: Bạn hãy viết chương trình tính thời gian nhỏ nhất (tính bằng giây) để Bé Bo thu được ít nhất ~x~ quả trứng.

Input

- Dòng thứ nhất chứa hai số nguyên dương ~n, x~;

- ~n~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le n)~ chứa hai số nguyên dương ~p_i~, ~t_i~ (~1 \le p_i, t_i \le 500~).

Output

Ghi ra một số nguyên duy nhất là thời gian nhỏ nhất để Bé Bo thu được ít nhất ~x~ quả trứng.

Scoring

Scoring table:

Sample Input 1

2 3
10 30
5 25

Sample Output 1

30

Sample Input 2

2 3
10 5
5 10

Sample Output 2

15

Notes

Ở ví dụ đầu tiên:

Con gà số ~1~ đẻ quả trứng đầu tiên ở giây ~10~, đẻ quả trứng thứ ~2~ ở giây ~40~, quả trứng thứ ~3~ ở giây ~70~, ...

Con gà số ~2~ đẻ quả trứng đầu tiên ở giây ~5~, đẻ quả trứng thứ ~2~ ở giây ~30~, quả trứng thứ ~3~ ở giây ~55~, ...

Vậy chỉ sau ~30~ giây thì tổng số trứng thu được là ~3~ quả.

Ở ví dụ thứ hai:

Con gà số ~1~ đẻ quả trứng đầu tiên ở giây ~10~, đẻ quả trứng thứ ~2~ ở giây ~15~, ...

Con gà số ~2~ đẻ quả trứng đầu tiên ở giây ~5~, đẻ quả trứng thứ ~2~ ở giây ~15~, ...

Vậy:

Tổng số trứng thu được sau ~5~ giây: ~1~

Tổng số trứng thu được sau ~10~ giây: ~2~

Tổng số trứng thu được sau ~15~ giây: ~4~