题目描述

有一个环形数组 $a_{1\sim n}$，即认为 $n$ 与 $1$ 相邻。

一次操作可以选择相邻的两个位置，将其中一个元素减一，并将另一个相邻元素加一。也就是说，数值可以沿环上的一条边移动一个单位，每移动一个单位记一次操作。

每个位置 $i$ 有目标区间 $[l_i,r_i]$。请计算使得所有 $a_i$ 都落在目标范围内所需的最小操作次数。

题目保证一定有解。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行，每行三个非负整数 $a_i,l_i,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

数据范围与约定

本题使用捆绑测试。

对于 $100\%$ 的数据，保证：

• $3\le n\le 2\times 10^5$；
• $0\le \sum l_i\le \sum a_i\le \sum r_i$；
• $0\le a_i\le 10^4$；
• $0\le l_i\le r_i\le 10^5$；
• 输入中的所有数据均为非负整数。