Матеуш любит путешевствовать! Однако, на его \(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\) монет, загадка будет решена и команда Матеуша выиграет!
Матеуш нацелен на как можно лучшее время. Разумеется, он хочет решить загадку как можно быстрее. Какое минимальное количество действий требуется совершить, чтобы удовлетворить всем условиям?
Выходные данные
Выведите одно целое число — минимальное количество операций, которое нужно сделать, чтобы решить загадку.