Вы играете в компьютерную игру. Для прохождения текущего уровня вам нужно убить полчище монстров. Среди него есть \(n\) монстров стоящих в ряд, пронумерованных от \(1\) по \(n\). У \(i\)-го монстра есть \(a_i\) здоровья и специальное заклинание «Подарок смерти» мощности \(b_i\).
Вы собираетесь убивать монстров по одному. Для убийства монстра со здоровьем \(h\) необходимо ровно \(h\) секунд.
Когда \(i\)-й монстр погибает, он использует свое заклинание, которое увеличивает здоровье своих соседей на \(b_i\) (соседями \(j\)-го монстра в ряду являются монстры на позициях \(j - 1\) и \(j + 1\). У первого и последнего монстров только по одному соседу).
После смерти каждого монстра, ряд смыкается, то есть соседи убитого монстра становятся соседями друг друга (соответственно, заклинание одного из соседей будет влиять на другого). Например, представим ситуацию с \(4\) монстрами со здоровьем \(a = [2, 6, 7, 3]\) и заклинаниями \(b = [3, 6, 0, 5]\). Один из способов уничтожения монстров показан ниже:
| \(2\) | \(6\) | \(7\) | \(3\) | \(\xrightarrow{6\ s}\) | \(8\) | \(13\) | \(3\) | \(\xrightarrow{13\ s}\) | \(8\) | \(3\) | \(\xrightarrow{8\ s}\) | \(6\) | \(\xrightarrow{6\ s}\) | \(\{\}\) |
| \(3\) | \(6\) | \(0\) | \(5\) | \(3\) | \(0\) | \(5\) | \(3\) | \(5\) | \(5\) | |
Первая строка описывает здоровье монстров, а вторая — силу их заклинаний. В результате мы можем уничтожить всех монстров за \(6 + 13 + 8 + 6\) \(=\) \(33\) секунды. Заметим, что это только пример и он может не являться самым быстрым из вариантов уничтожения.
Какое наименьшее время вам понадобиться для убийства всего ряда монстров?
Выходные данные
Для каждого набора входных данных выведите одно число — наименьшее возможное суммарное время уничтожения всех монстров.
Примечание
В первом наборе входных данных есть только один монстр, который будет убит за \(10\) секунд.
Во втором наборе, выгодно убить сначала первого монстра, потом последнего, а затем среднего. Уничтожение монстров займет \(100 + 100 + (1 + 1 + 1)\) \(=\) \(203\) секунд.
В третьем наборе, выгодно сначала убить первого монстра, потом третьего, затем четвертого, и, наконец, второго. Уничтожение всех займет \(2 + 7 + (3 + 0) + (3 + 6 + 5)\) \(=\) \(26\) секунд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
10
0
3
100 1 100
1 100 1
4
2 6 7 3
3 6 0 5
2
1000000000 1000000000
1000000000 1000000000
|
10
203
26
3000000000
|