Вы играете в очередную компьютерную игру, и теперь вам предстоит убить \(n\) монстров. Эти монстры стоят в круге, пронумерованном по часовой стрелке от \(1\) до \(n\). Изначально \(i\)-й монстр имеет \(a_i\) единиц здоровья.
Вы можете стрелять в монстров, чтобы убить их. Каждый выстрел требует ровно одной пули и уменьшает здоровье монстра на \(1\) (наносит ему \(1\) единицу урона). Кроме того, когда здоровье некоторого монстра \(i\) становится \(0\) или меньше \(0\), он умирает и взрывается, нанося \(b_i\) урон следующему монстру (монстру под номером \(i + 1\), если \(i < n\), или монстру под номером \(1\), если \(i = n\)). Если следующий монстр уже мертв, то ничего не происходит. Если взрыв убивает следующего монстра, он тоже взрывается, повреждая монстра после него и, возможно, вызывая еще один взрыв, и так далее.
Вы должны посчитать минимальное количество пуль, которое нужно выстрелить, чтобы убить всех \(n\) монстров в кругу.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество пуль, которые нужно выстрелить, чтобы убить всех монстров.