output_description: Print Tak's total accommodation fee.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N
      K
      X
      Y
attempt: def solve():
      def recur(i, n, total):
          # print("i, n, total", i, n, total)
  
          if not TABLE[i][n][total] == -1:
              # print('cache!')
              return TABLE[i][n][total]
  
          if not i < N:
              if n > 0 and total == A * n:
                  TABLE[i][n][total] = 1
                  return 1
              TABLE[i][n][total] = 0
              return 0
  
          ans1 = recur(i + 1, n, total)
          ans2 = recur(i + 1, n + 1, total + XS[i])
  
          # print(ans1, ans2)
  
          return ans1 + ans2
  
      N, A = tuple(map(int, input().split()))
      XS = tuple(map(int, input().split()))
  
      TABLE = []
      for _ in range(N + 1):
          lines = [[-1 for x in range(N * 50 + 1)] for y in range(N + 1)]
          TABLE.append(lines)
  
      return recur(0, 0, 0)
  
  
  if __name__ == "__main__":
      print(solve())
  
problem_description: Statement
  
  There is a hotel with the following accommodation fee:
  
    * X yen (the currency of Japan) per night, for the first K nights
    * Y yen per night, for the (K+1)-th and subsequent nights
  
  Tak is staying at this hotel for N consecutive nights. Find his total
  accommodation fee.
samples: [{"input": "5\n    3\n    10000\n    9000", "output": "48000\n    \n\nThe accommodation fee is as follows:\n\n  * 10000 yen for the 1-st night\n  * 10000 yen for the 2-nd night\n  * 10000 yen for the 3-rd night\n  * 9000 yen for the 4-th night\n  * 9000 yen for the 5-th night\n\nThus, the total is 48000 yen.\n\n* * *"}, {"input": "2\n    3\n    10000\n    9000", "output": "20000"}]