Недавно Коля узнал, что скоро в его городе откроется новый кинотеатр, который будет показывать новый фильм каждый день на протяжении \(n\) дней. Так, в день номер \(1 \le i \le n\), кинотеатр покажет премьеру \(i\)-го фильма. Коля узнал расписание фильмов и сопоставил каждому фильму его интересность — целую величину \(a_i\).
Однако даже самые интересные фильмы не будут казаться такими, если фильмы долго не смотреть, поэтому интересность очередного фильма снизится на \(d \cdot cnt\), где \(d\) — заранее определенная величина, а \(cnt\) — кол-во дней с последнего посещения кинотеатра. Также известно, что Коля успел посетить другой кинотеатр за день до открытия нового — в день номер \(0\). Так, если мы впервые посетим кинотеатр в день с номером \(i\), то \(cnt\) — кол-во дней с последнего посещения кинотеатра будет равно \(i\).
Так, например, если \(d = 2\), а \(a = [3, 2, 5, 4, 6]\), то посетив фильмы с номерами \(1\) и \(3\), значение \(cnt\) для дня номер \(1\) будет равно \(1 - 0 = 1\), а значение \(cnt\) для дня номер \(3\) будет равно \(3 - 1 = 2\), так суммарная интересность фильмов будет \(a_1 - d \cdot 1 + a_3 - d \cdot 2 = 3 - 2 \cdot 1 + 5 - 2 \cdot 2 = 2\).
К несчастью, у Коли есть время только на то, чтобы посетить не более \(m\) фильмов. Помогите ему составить план посещения кинотеатра так, чтобы суммарная интересность всех посещенных им фильмов была максимальна.
Примечание
Первый пример разобран в условии.
Во втором примере, оптимально не посещать никакие фильмы.
В третьем наборе входных данных оптимально посетить фильмы с номерами \(2\), \(3\), \(5\), \(6\), тогда суммарная интересность посещенных фильмов составит \(45 - 6 \cdot 2 + 1 - 6 \cdot 1 + 39 - 6 \cdot 2 + 11 - 6 \cdot 1 = 60\).