import sys import heapq def main(): sys.setrecursionlimit(1 << 25) N, K = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) # We represent the array as a list of segments. # Each segment is a tuple: (start, end, shift, max_even, max_even_pos) # Initially, the array is one segment covering 0..N-1 with shift 0. segments = [] heapq.heapify(segments) # We push the initial segment with a dummy value. The actual max_even is computed later. heapq.heappush(segments, (0, -1, 0, 0, 0)) # (max_even, index, shift, start, end) # segments is a max-heap, so we store negative values. # To handle the correct order, we'll process the segments and compute their max_even. # However, since we need to process all segments to compute their max_even, perhaps it's better to build the initial segments correctly. # Rebuilding the approach: Each segment is a start and end index in the original array, with a shift value indicating the number of elements removed before it. The max_even is the maximum A_i in even positions (considering the shift). # Let's build the initial segments correctly. # We'll represent each segment with a start and end (original indices), and a shift (number of elements removed before this segment). The max_even is the maximum A_i in even positions (original index - shift). initial_segment = (0, N-1, 0, 0, 0) # (start, end, shift, max_even, max_even_pos) initial_max = 0 initial_max_pos = -1 for i in range(initial_segment[0], initial_segment[1]+1): current_pos = i - initial_segment[2] if current_pos % 2 == 1: # 1-based even is 2,4,... which is 0-based index 1,3, etc. if A[i] > initial_max: initial_max = A[i] initial_max_pos = i initial_segment = (0, N-1, 0, initial_max, initial_max_pos) heapq.heappush(segments, (-initial_segment[3], initial_segment[0], initial_segment[1], initial_segment[2], initial_segment[4])) sum_total = 0 for _ in range(K): if not segments: break # should not happen as K <= N-1 current = heapq.heappop(segments) current_max = -current[0] start = current[1] end = current[2] shift = current[3] max_pos = current[4] if max_pos == -1: # No even position in this segment, so skip continue sum_total += A[max_pos] # Now, split this segment into left and right left_start = start left_end = max_pos - 1 right_start = max_pos + 1 right_end = end # Update left segment if left_start <= left_end: # Compute max_even for left segment new_shift = shift max_even = 0 max_even_pos = -1 for i in range(left_start, left_end + 1): current_pos = i - new_shift if current_pos % 2 == 1: if A[i] > max_even: max_even = A[i] max_even_pos = i # Push left segment into heap if max_even != 0 or max_even_pos != -1: heapq.heappush(segments, (-max_even, left_start, left_end, new_shift, max_even_pos)) # Update right segment if right_start <= right_end: # Compute max_even for right segment new_shift = shift + 1 # because max_pos is removed, elements to the right have their positions shifted left by 1 max_even = 0 max_even_pos = -1 for i in range(right_start, right_end + 1): current_pos = i - new_shift if current_pos % 2 == 1: if A[i] > max_even: max_even = A[i] max_even_pos = i # Push right segment into heap if max_even != 0 or max_even_pos != -1: heapq.heappush(segments, (-max_even, right_start, right_end, new_shift, max_even_pos)) print(sum_total) if __name__ == '__main__': main()