Лимак — старый бурый мишка. Он часто ходит в боулинг с друзьями. Сегодня он чувствует себя очень хорошо и старается побить собственный рекорд!
За бросок он получает целое число (возможно, отрицательное) очков. В конце игры счет за i-й бросок умножается на i и все счета суммируются. Таким образом, за k бросков на s1, s2, ..., sk очков общий счёт будет равен 
. В частности, если бросков не было, общий счёт полагается равным 0.
Лимак сделал n бросков и получил счет ai за i-й из них. Он хочет максимизировать свой общий счет и придумал интересную мысль. Он отменит некоторые броски, сказав, что его что-то отвлекло или что дул сильный ветер.
Лимак может отменить любое количество бросков (возможно, все или ни один из них). Общий счет подсчитывается так, как будто были только не отмененные броски (прочитайте пояснения к тестам). Какой максимальный общий счет может получить Лимак?
Примечание
В первом примере Лимак должен отменить броски со счетами - 8 и - 3. Затем у него останутся три броска со счетами - 2, 0, 5. Общий счет — 1·( - 2) + 2·0 + 3·5 = 13.
Во втором примере Лимак должен отменить бросок со счетом - 50. Общий счет равен 1·( - 10) + 2·20 + 3·( - 30) + 4·40 + 5·60 = 400.