Có ~n~ gói kẹo, gói thứ ~i~ có ~a_i~ viên kẹo. Cần thu được ~m~ gói có số kẹo bằng nhau bằng các thao tác chuyển đúng một viên kẹo từ một gói sang một gói khác. Mỗi thao tác mất một giây.

Hãy tìm thời gian tối thiểu cần thiết.

Input

Dòng đầu chứa hai số nguyên dương ~n,m~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~.

Output

In ra số giây tối thiểu.

Subtask

• 40% số điểm: ~n \le 1000~, ~a_i \le 1000~.
• 30% số điểm: ~n \le 1000~, ~a_i \le 10^9~.
• 30% số điểm: ~1 \le m<n \le 10^6~, ~a_i \le 10^9~.</li>

Ví dụ

4 3
6 3 8 9

2