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: #!/usr/bin/env python3
  import sys, math, fractions, itertools
  
  
  def solve(N: int, A: int, x: "List[int]"):
      X = max(x)
      dp = [
          [[0 for _ in range(max(N * X + 1, N * A + 1))] for _ in range(N + 1)]
          for _ in range(N + 1)
      ]
      dp[0][0][0] = 1
      for n in range(N + 1):
          for m in range(N + 1):
              for k in range(N * X + 1):
                  if n >= 1 and k < x[n - 1]:
                      dp[n][m][k] = dp[n - 1][m][k]
                  elif n >= 1 and m >= 1 and k >= x[n - 1]:
                      dp[n][m][k] = dp[n - 1][m][k] + dp[n - 1][m - 1][k - x[n - 1]]
      s = 0
      for i in range(1, N + 1):
          s += dp[N][i][i * A]
      print(s)
      return
  
  
  # Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
  def main():
      def iterate_tokens():
          for line in sys.stdin:
              for word in line.split():
                  yield word
  
      tokens = iterate_tokens()
      N = int(next(tokens))  # type: int
      A = int(next(tokens))  # type: int
      x = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
      solve(N, A, x)
  
  
  if __name__ == "__main__":
      main()
  
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"}]