{"problem":{"name":"Blue Spring","description":{"content":"Takahashi is planning an $N$\\-day train trip.   For each day, he can pay the regular fare or use a one-day pass. Here, for $1\\leq i\\leq N$, the regular fare for the $i$\\-th day of the trip is $F_i$ ye","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc318_c"},"statements":[{"statement_type":"Markdown","content":"Takahashi is planning an $N$\\-day train trip.  \nFor each day, he can pay the regular fare or use a one-day pass.\nHere, for $1\\leq i\\leq N$, the regular fare for the $i$\\-th day of the trip is $F_i$ yen.  \nOn the other hand, a batch of $D$ one-day passes is sold for $P$ yen. You can buy as many passes as you want, but only in units of $D$.  \nEach purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.\nFind the minimum possible total cost for the $N$\\-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.\n\n## Constraints\n\n*   $1\\leq N\\leq 2\\times 10^5$\n*   $1\\leq D\\leq 2\\times 10^5$\n*   $1\\leq P\\leq 10^9$\n*   $1\\leq F_i\\leq 10^9$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $D$ $P$\n$F_1$ $F_2$ $\\ldots$ $F_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc318_c","tags":[],"sample_group":[["5 2 10\n7 1 6 3 6","20\n\nIf he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be $(10\\times 1)+(0+1+0+3+6)=20$, which is the minimum cost needed.  \nThus, print $20$."],["3 1 10\n1 2 3","6\n\nThe minimum cost is achieved by paying the regular fare for all three days."],["8 3 1000000000\n1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000","3000000000\n\nThe minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.  \nNote that the answer may not fit into a $32$\\-bit integer type."]],"created_at":"2026-03-03 11:01:14"}}