Công ty có duy nhất một xe để đón công nhân đi làm. Trụ sở công ty nằm ở đầu đường quốc lộ và dọc theo quốc lộ có ~ n ~ điểm tập trung nhân viên đánh số từ 1 tới ~ n ~. Điểm thứ ~ i ~ cách công ty ~ x_i ~ km ~ (x_1 < x_2 <⋯< x_n) ~ và có ~ a_i ~ người đứng đợi tại điểm ~ i ~. Xe không được chở quá ~ m ~ người, vì vậy để đón hết các nhân viên, xe phải đi nhiều lượt, mỗi lượt xe xuất phát từ trụ sở công ty, đi đón nhân viên và quay về trụ sở công ty.

Yêu cầu: Hãy lập hành trình cho xe đón tất cả các nhân viên sao cho quãng đường xe di chuyển là ít nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~ n, m ~ ~ (n ≤ 10^5, m ≤ 10^9) ~
• ~ n ~ dòng tiếp theo, dòng thứ ~ i ~ chứa hai số nguyên ~ x_i, a_i ~ ~ (x_i, a_i ≤ 10^9) ~

Kết quả

• Một số nguyên duy nhất là độ dài quãng đường xe cần di chuyển theo phương án tìm được

Ví dụ:

Input 1

2 4
1 2
5 6 

Output 1

20