Một cao nguyên có ~N~ điểm được đánh số từ ~1~ đến ~N~. Tại điểm thứ ~i~, có:

• Độ cao ban đầu ~H_i~.

• Chi phí xây thêm trạm nối ~C_i~, trạm nối có tác dụng kết nối hai địa điểm.

Ban đầu, mỗi điểm có ~1~ trạm nối chưa sử dụng. Người quản lý muốn xây dựng một khu trượt tuyết bằng cách chọn một điểm làm khách sạn, sau đó xây các đường trượt sao cho từ mọi điểm đều có thể đi về khách sạn.

Để thực hiện, có thể sử dụng các thao tác sau:

• Tăng độ cao: Chọn một điểm ~i~, tăng ~H_i~ lên ~1~ đơn vị. Chi phí cho mỗi lần tăng là ~K~.

• Xây thêm trạm nối: Tại điểm ~i~, xây thêm ~1~ trạm nối với chi phí ~C_i~.

Sau khi thực hiện các thao tác trên, tiến hành xây các đường trượt:

• Với mỗi điểm ~i~ (không phải khách sạn), chọn một điểm ~j~ sao cho:

  • ~H_j < H_i~.

  • Điểm ~j~ còn ít nhất ~1~ trạm nối chưa sử dụng.

• Dùng ~1~ trạm nối tại ~j~ để xây đường trượt một chiều từ ~i \rightarrow j~.

Yêu cầu: Hãy tính chi phí nhỏ nhất để xây dựng khu trượt tuyết sao cho từ mọi điểm đều có thể đi tới khách sạn.

Input

Dòng đầu ghi hai số nguyên ~N, K~ ~(1 \le N \le 300,\ 1 \le K \le 10^9)~.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~H_i, C_i~ ~(0 \le H_i \le 10^9;\ 1 \le C_i \le 10^9)~.

Output

Một số nguyên duy nhất là chi phí nhỏ nhất cần thiết.

Scoring

Sample Input 1

5 2
0 6
1 1
0 5
2 1
1 2

Sample Output 1

8

Notes

Tăng độ cao điểm ~1~ hai lần và điểm ~5~ một lần với chi phí ~6~ để đạt độ cao ~2, 1, 0, 2, 2~, chọn điểm ~3~ làm khách sạn, sau đó xây thêm ~2~ trạm nối tại điểm ~2~ với chi phí ~2~ để đủ số trạm, rồi xây các đường trượt ~1 \rightarrow 2~, ~2 \rightarrow 3~, ~4 \rightarrow 2~, ~5 \rightarrow 2~. Tổng chi phí tối ưu là ~6 + 2 = 8~.