Trong một ngày mùa thu tuyệt đẹp, Bờm và Cuội nhận thấy rằng con hẻm trong vườn nơi họ hay dạo chơi cùng nhau có khá nhiều lá. Họ quyết định gom thành đúng 𝐾 đống lá.

Có 𝑛 chiếc lá nằm thẳng hàng với trọng lượng khác nhau, khoảng cách giữa hai chiếc lá liên tiếp bằng 1. Nghĩa là, chiếc lá đầu tiên có tọa độ 1, chiếc lá thứ hai có tọa độ 2, ..., chiếc lá thứ 𝑛 có tọa độ 𝑛.

Bờm và Cuội thực hiện việc gom lá trước khi rời khỏi vườn, do vậy những chiếc lá chỉ có thể di chuyển về phía bên trái. Chi phí di chuyển một chiếc lá bắng tích của trọng lượng chiếc lá và khoảng cách di chuyển. Hiển nhiên một trong 𝐾 đống lá sẽ nằm ở tọa độ 1, tuy nhiên những đống lá còn lại có thể nằm ở bất kỳ vị trí nào.

Yêu cầu: Tìm chi phí nhỏ nhất để di chuyển 𝑛 chiếc lá thành đúng 𝐾 đống.

Input:

• Dòng 1: Chứa hai số nguyên dương 𝑛,𝐾 (𝑛≤~10^5~,𝐾≤10,𝐾<𝑛)

• Dòng 2: Chứa n số nguyên ~𝑎_1~,~𝑎_2~,…,~𝑎_𝑛~ (1≤~𝑎_𝑖~≤100) lần lượt là trọng lượng của các lá 1, 2, ..., 𝑛

Output: Một số nguyên là chi phí nhỏ nhất để gom 𝑛 chiếc lá thành đúng 𝐾 đống

VÍ DỤ:

INPUT

5 2 1 2 3 4 5

OUTPUT

13

Subtasks:

• Subtask 1: 𝑛≤1000 [50%]

• Subtask 2: 𝑛≤100000 [50%]