output_description: Print the maximum possible total score for Takahashi's throws.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N M K
      A_1 A_2 … A_N
attempt: from collections import deque
  import sys
  
  
  def solve():
      readline = sys.stdin.readline
  
      N, M, K = map(int, readline().split())
      (*A,) = map(int, readline().split())
  
      S = A[:]
      T = [0] * N
      for k in range(K - 1):
          que = deque()
          for i, a in enumerate(S[:-1]):
              while que and que[-1][1] <= a:
                  que.pop()
              que.append((i, a))
  
              T[i + 1] = que[0][1] + A[i + 1] * (k + 2)
  
              if que and que[0][0] <= i + 1 - M:
                  que.popleft()
          S, T = T, S
      print(max(S))
  
  
  solve()
  
problem_description: Statement
  
  There are N panels arranged in a row in Takahashi's house, numbered 1 through
  N. The i-th panel has a number A_i written on it. Takahashi is playing by
  throwing balls at these panels.
  
  Takahashi threw a ball K times. Let the panel hit by a boll in the i-th throw
  be panel p_i. He set the score for the i-th throw as i \times A_{p_i}.
  
  He was about to calculate the total score for his throws, when he realized
  that he forgot the panels hit by balls, p_1,p_2,...,p_K. The only fact he
  remembers is that for every i (1 ≦ i ≦ K-1), 1 ≦ p_{i+1}-p_i ≦ M holds. Based
  on this fact, find the maximum possible total score for his throws.
samples: [{"input": "5 2 3\n    10 2 8 10 2", "output": "56\n    \n\nThe total score is maximized when panels 1,3 and 4 are hit, in this order.\n\n* * *"}, {"input": "5 5 2\n    5 2 10 5 9", "output": "28\n    \n\nThis case satisfies the additional constraint M = N for a partial score.\n\n* * *"}, {"input": "10 3 5\n    3 7 2 6 9 4 8 5 1 1000000000", "output": "5000000078"}]