Последний рейс эвакуатора
На космической трассе расположены N станций. На станции с номером i находится ai контейнеров, которые необходимо эвакуировать.
Робот-эвакуатор может начать рейс с любой станции с номером i. После этого он последовательно посещает все станции от i до N включительно и забирает все контейнеры на них.
За каждый спасённый контейнер начисляется один кредит. Но для рейса необходимо арендовать оборудование, стоимость которого равна K, умноженному на наибольшее число контейнеров на одной из посещённых станций.
Прибыль равна числу полученных кредитов минус стоимость аренды. Можно отказаться от рейса, если все варианты дают неположительную прибыль.
Найдите станцию, с которой выгоднее всего начать рейс, и максимальную положительную прибыль. Если станций с одинаковой максимальной прибылью несколько, выберите станцию с наименьшим номером. Если положительная прибыль невозможна, выведите 0 0.
Входные данные
В первой строке записаны два целых числа N и K (1 ≤ N ≤ 200000, 1 ≤ K ≤ 1000000).
Во второй строке записаны N целых чисел ai (0 ≤ ai ≤ 1000000).
Выходные данные
Выведите через пробел номер начальной станции и максимальную прибыль либо 0 0, если выгодного рейса нет.
| № | Входные данные | Выходные данные |
|
1
|
6 2
20 4 4 4 4 4
|
2 12
|