Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount. You are given an array a of length n and an integer c . The value of some array b of length k is the sum of its elements except for the smallest. For example, the value of the array 3, 1, 6, 5, 2 with c = 2 is 3 + 6 + 5 = 14 . Among all possible partitions of a into contiguous subarrays output the smallest possible sum of the values of these subarrays. The first line contains integers n and c ( 1 ≤ n , c ≤ 100 000 ). The second line contains n integers a i ( 1 ≤ a i ≤ 10 9 ) — elements of a . Output a single integer — the smallest possible sum of values of these subarrays of some partition of a . In the first example any partition yields 6 as the sum. In the second example one of the optimal partitions is 1, 1, 10, 10, 10, 10, 10, 10, 9, 10, 10, 10 with the values 2 and 90 respectively. In the third example one of the optimal partitions is 2, 3, 6, 4, 5, 7, 1 with the values 3, 13 and 1 respectively. In the fourth example one of the optimal partitions is 1, 3, 4, 5, 5, 3, 4, 1 with the values 1, 21 and 1 respectively.