Матеуш любит путешевствовать! Однако, на его $$$42$$$-м визите Санкт-Компьютерсбурга осталось не так много достопримечательностей для осмотра. Поэтому он решил отправиться со своими друзьями в эскейп-рум!

Команда с легкостью разгадала почти все загадки. Осталось только одна — большой круглый стол! Есть $$$n$$$ весов, лежащих на поверхности стола, распределенных по окружности. Каждые весы соседствуют ровно двум другим весами: для каждого $$$i \in \{1, 2, \dots, n-1\}$$$, $$$i$$$-е и $$$(i+1)$$$-е весы являются соседними, а также соседними являются первые и $$$n$$$-е весы.

Изначально на $$$i$$$-х весах лежат $$$a_i$$$ тяжелых монет. Матеуш может совершать движения — каждое движение состоит из взятия одной монеты с одних весов и перекладывания ее на соседние весы.

Оказывается, что загадка будет решена только если соблюдаются некоторые условия на количества монет на каждых весах. А именно, у каждых весов есть параметры $$$l_i$$$ и $$$r_i$$$. Если каждая монета лежит на ровно одних весах, и для каждого $$$i$$$, на $$$i$$$-х весах лежат хотя бы $$$l_i$$$ и не более $$$r_i$$$ монет, загадка будет решена и команда Матеуша выиграет!

Матеуш нацелен на как можно лучшее время. Разумеется, он хочет решить загадку как можно быстрее. Какое минимальное количество действий требуется совершить, чтобы удовлетворить всем условиям?