Васе на телефон в ближайшее время придет n сообщений. Сообщение с номером i придёт через ti минут. У каждого сообщения есть цена, которая изначально равна A. После того, как сообщение пришло Васе, его цена уменьшается на B каждую минуту, и в том числе может стать отрицательной. В любой момент времени Вася может прочитать любые сообщения. Когда Вася читает сообщение, к его счету добавляется текущая цена этого сообщения. Изначально счёт Васи равен 0.
Кроме того, каждую минуту к счёту Васи прибавляется C·k, где k — количество уже полученных, но ещё не прочитанных сообщений.
Поскольку сообщения очень важны для Васи, он хочет, чтобы через T минут все сообщения были прочитаны.
Определите, какой максимальный счёт может быть у Васи через T минут.
Выходные данные
Выведите одно целое число — ответ на задачу.
Примечание
В первом примере сообщения нужно прочитать сразу, Вася получит A очков за каждое сообщение, то есть всего n·A = 20 очков.
Во второй примере сообщения можно прочитать в любой целочисленный момент.
В третьем примере сообщения нужно прочитать в момент времени T. Тогда у Васи будет 1, 2, 3, 4 и 0 непрочитанных сообщений в соответствующие минуты, он получит 40 очков за них. Когда он прочитает сообщения, он получит (5 - 4·3) + (5 - 3·3) + (5 - 2·3) + (5 - 1·3) + 5 = - 5 очков, что даст итоговый счет 35.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5 5 3 5
1 5 5 4
|
20
|
|
2
|
5 3 1 1 3
2 2 2 1 1
|
15
|
|
3
|
5 5 3 4 5
1 2 3 4 5
|
35
|