Mateusz 喜欢旅行!然而,在他 $$$42$$$ 第一次访问圣计算机堡时,没有什么可参观的了。所以他决定和朋友们一起去密室逃脱!
团队完美地解决了所有谜题。只剩下一个谜语了——一张巨大的圆桌!桌子上有 $$$n$$$ 秤,沿着圆圈分布。每个尺度恰好与其他两个尺度相邻:对于每个 $$$i \in \{1, 2, \dots, n-1\}$$$,第 $$$i$$$ 和第 $$$(i+1)$$$ 尺度彼此相邻,第一个尺度和第 $$$n$$$ 尺度也是如此。
第 $$$i$$$ 秤最初包含 $$$a_i$$$ 重硬币。 Mateusz 可以执行移动——每个移动包括从一个秤上取出一枚硬币并将其放在任何相邻的秤上。
事实证明,当每个秤上都有特定数量的硬币时,谜题就会被解决。具体来说,每个尺度都有参数$$$l_i$$$ 和$$$r_i$$$。如果每个硬币都放在一个秤上,并且对于每个 $$$i$$$,第 $$$i$$$ 秤至少包含 $$$l_i$$$ 且最多 $$$r_i$$$ 硬币,则谜题将被解决,Mateusz 的团队将获胜!
Mateusz 的目标是尽可能最好的时间。所以,他想要尽快解开这个谜题。满足所有条件所需的最少移动次数是多少?
输入
第一行包含一个整数 $$$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$$$。
输出
输出一个整数——解开谜题所需的最少运算次数。
示例
输入 #1
5 0 2 3 1 2 3 4 3 3 4 3 3 4 3 3
输出 #1
4
输入 #2
3 0 1 2 3 0 3 1 0 0
输出 #2
1
输入 #3
4 1 0 2 3 3 3 4 0 4 5 3 5
输出 #3
0