题面题面语言简体中文expand_more한국어English日本語简体中文有 NNN 座拉面工厂，依次编号为 111 到 NNN。教俊希望从工厂 iii 恰好购买 AiA_iAi 包拉面。 每次购买时，他可以选择不超过 KKK 座连续的工厂，并从每座选中的工厂购买一包拉面。如果选择了 ℓ\ellℓ 座工厂，本次购买的费用为 B+(ℓ−1)CB+(\ell-1)CB+(ℓ−1)C 韩元。 求购买全部所需拉面的最小总费用。输入输入格式如下：N K B CN\ K\ B\ CN K B C A1 A2 ⋯ ANA_1\ A_2\ \cdots\ A_NA1 A2输出输出最小总费用。限制 1≤N≤200 0001\le N\le 200\,0001≤N≤200000 1≤K≤N1\le K\le N1≤K≤N 0≤Ai≤1060\le A_i\le 10^6 (). 样例样例 1样例输入复制3 3 3 1 1 2 1样例输出复制8样例 2样例输入复制2 2 1 3 2 1样例输出复制3样例 3样例输入复制1 1 1000000 1 0样例输出复制0显示标签
