Có $n$ người đến dùng bữa tại một nhà hàng, họ được đánh số từ $1$ đến $n$ . Nhà hàng có tổng cộng $m$ chỗ ngồi, do đó số người dùng bữa cùng lúc không được vượt quá $m$ .

Cho biết thời điểm đến nhà hàng và thời gian cần để dùng bữa của $n$ người; thời điểm đến và thời gian dùng bữa của người thứ $i$ lần lượt là $a_i$ và $b_i$ , đảm bảo $a_1 < a_2 < ... < a_n$ .

Khi nhà hàng đã kín chỗ, những người đến sau phải chờ bên ngoài; ngay khi có người dùng bữa xong rời đi và tạo ra chỗ trống, người đang chờ bên ngoài sẽ lập tức vào; nếu có nhiều người cùng chờ thì người có số thứ tự nhỏ hơn được vào trước.

Hãy tính tổng của thời gian chờ + thời gian dùng bữa của tất cả mọi người.

Dữ liệu vào

Dòng đầu tiên nhập hai số nguyên dương $n, m$ .

Từ dòng thứ $2$ đến dòng thứ $n+1$ , mỗi dòng gồm hai số nguyên; dòng thứ $i+1$ tương ứng với thời điểm đến $a_i$ và thời gian dùng bữa $b_i$ của người thứ $i$ .

Dữ liệu ra

In ra một số nguyên, biểu thị tổng của thời gian chờ cộng thời gian dùng bữa của tất cả mọi người.

Ví dụ

Input

3 2
1 5
2 5
3 5

Output

18

Ghi chú

Giải thích ví dụ

• Người số 1: không phải chờ, thời gian ăn 5, tổng thời gian 5

• Người số 2: không phải chờ, thời gian ăn 5, tổng thời gian 5

• Người số 3: thời gian chờ 3, thời gian ăn 5, tổng thời gian 8

• Tổng cộng: $5+5+8=18$

Giới hạn dữ liệu

• Với 50% dữ liệu chấm: $1 \le n, m \le 10^4$

• Với 100% dữ liệu chấm: $1 \le n, m \le 10^5$ , $1 \le a_i, b_i \le 10^6$