Để giải quyết vấn đề ùn tắc giao thông thường xuyên trên một con đường Đông - Tây ở tỉnh A, chính quyền tỉnh đã mở một cuộc điều tra. Sau khi điều tra được biết, hai bên đường có nhiều thôn, bản là nơi có nhiều tín đồ theo đạo \(C\). Cứ chủ nhật, họ lại tự lái ô tô dọc đường về \(B\) để cúng bái vị thần linh của mình, đó là nguyên nhân dẫn đến tình trạng kẹt xe.

Một cuộc điều tra chi tiết cho thấy có tổng cộng \(N\) làng ở đây, và tất cả đều ở phía Đông \(B\). Tại làng thứ \(i\) có \(R_i\) là tín đồ theo đạo \(C\), và khoảng cách từ nơi đó đến \(B\) là \(T_i\) (đơn vị: km). Để giải quyết vấn đề này, chính quyền tỉnh \(A\) đã quyết định xây dựng một tuyến đường sắt cao tốc ngầm, bên dưới tuyến đường cao tốc này để dễ lưu thông và xây dựng một số nhà ga dọc tuyến (ga xuất phát sẽ được xây dựng tại khu vực \(B\), không được tính là nhà ga).

Trước tiên, mỗi tín đồ sẽ lái xe theo hướng \(B\) (nếu tình cờ có ga trong làng của mình, anh ta không cần lái xe), chuyển đến ga đường sắt cao tốc gần nhất (nếu anh ta lái xe thẳng đến B thì không cần chuyển), và sau đó đi đường sắt cao tốc đến \(B\). Nhưng chính phủ \(A\) có một vấn đề cần đặt ra: xây bao nhiêu trạm và xây ở đâu? Trong đề án xây dựng ga, xây quá nhiều ga sẽ tốn quá nhiều kinh phí, nhưng xây quá ít ga hoặc xây sai vị trí sẽ gây ùn tắc giao thông. Để phối hợp hai khía cạnh này, chính phủ sử dụng phương pháp cho điểm để đo lường chất lượng của một kế hoạch (điểm càng lớn thì kế hoạch càng xấu): cứ mỗi lần xây dựng một nhà ga, m điểm sẽ được cộng thêm, không xét lại), 1 điểm sẽ được cộng cho mỗi 1 km do người dân tự lái xe.

Yêu cầu: Em hãy thiết kế phương án xây dựng nhà ga sao cho số điểm là nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\).

• \(n\) dòng tiếp theo, mỗi dòng có hai số nguyên dương \(T_i\) và \(R_i\) .

Dữ liệu ra:

• Xuất ra một số nguyên là số điểm nhỏ nhất cần tìm.

Ràng buộc

• Subtask 1: 30% test có \( n ≤ 100, m ≤ 1000, T_i ≤ 1000, R_i ≤ 1000. \)

• Subtask 2: 70% test có \(n ≤ 4.10^4, m ≤ 2.10^9, T_i ≤ 10^6, R_i ≤ 10^3\)

Sample Input

4 30
25 3
5 3
25 2
20 5

Sample Output

70

Giải thích

Trong ví dụ, nếu một trạm được xây dựng cách nơi \(B\) \(20\)km, những tín đồ ở thôn 4 không phải lái xe, và số điểm là 30 điểm. Các tín đồ ở thôn 1 và thôn 3 lần đầu chạy xe đến bến cách địa điểm B 20km, ghi được 3 5 + 2 5 = 25 điểm. Các tín đồ ở Làng số 2 đã lái xe thẳng đến địa điểm B và ghi được 3 * 5 = 15 điểm. Tổng cộng có 70 điểm được ghi.