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