Mùa hè năm nay quá nóng, ledinhbaonam và uia quyết định xây một trung tâm hỗ trợ du khách trên quần đảo để tránh việc người dân phải di chuyển quá xa trong thời tiết oi bức.

Quần đảo gồm \(N\) hòn đảo được đánh số từ \(1\) đến \(N\) và nằm thẳng hàng theo đúng thứ tự đánh số.

Trên đảo thứ \(i\) có \(D_i\) người dân sinh sống.

Trung tâm hỗ trợ được xây tại đúng một hòn đảo.

Nếu trung tâm được xây tại đảo \(x\), thì một người dân trên đảo \(i\) được xem là phải di chuyển quá xa nếu:

Toàn bộ \(D_i\) người dân trên đảo đó sẽ bị tính vào số người phải di chuyển quá xa.

Nhiệm vụ

Hãy chọn vị trí xây trung tâm sao cho tổng số người dân phải di chuyển quá xa là nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên \(N, K\) \((1 \le N \le 2 \cdot 10^5,\ 0 \le K \le N)\)

• Dòng thứ hai chứa \(N\) số nguyên: \(D_1,D_2,\ldots,D_N\) \((0 \le D_i \le 10^4)\)

Output

• In ra số người dân ít nhất phải di chuyển quá xa.

Example

5 1
1 2 1 3 2

3

8 2
3 1 4 1 5 9 2 6

8