G. Матеуш и эскейп-рум
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Матеуш любит путешевствовать! Однако, на его $$$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$$$ монет, загадка будет решена и команда Матеуша выиграет!

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

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$3 \le n \le 35\,000$$$) — количество весов на круге.

Следующие $$$n$$$ строк описывают весы. $$$i$$$-я из них описывает $$$i$$$-е весы и содержит три целых числа $$$a_i, l_i, r_i$$$ ($$$0 \le a_i \le 35\,000$$$, $$$0 \le l_i \le r_i \le 35\,000$$$).

Гарантируется, что загадка разрешима, а именно $$$\sum_{i=1}^n l_i \le \sum_{i=1}^n a_i \le \sum_{i=1}^n r_i$$$.

Выходные данные

Выведите одно целое число — минимальное количество операций, которое нужно сделать, чтобы решить загадку.

Примеры
Входные данные
5
0 2 3
1 2 3
4 3 3
4 3 3
4 3 3
Выходные данные
4
Входные данные
3
0 1 2
3 0 3
1 0 0
Выходные данные
1
Входные данные
4
1 0 2
3 3 3
4 0 4
5 3 5
Выходные данные
0