{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $D$ $P$\n$F_1$ $F_2$ $\\ldots$ $F_N$"},{"iden":"sample input 1","content":"5 2 10\n7 1 6 3 6"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"3 1 10\n1 2 3"},{"iden":"sample output 2","content":"6\n\nThe minimum cost is achieved by paying the regular fare for all three days."},{"iden":"sample input 3","content":"8 3 1000000000\n1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000"},{"iden":"sample output 3","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}