#P17973. K-Coverage
K-Coverage
K-Coverage
题目描述
非负数轴上有 条等长线段。第 条线段的左端点为 ,覆盖闭区间 。
你可以移动至多一条线段:将它的左端点改成任意非负整数,线段长度保持不变。移动后的左端点没有上界限制。 也可以不移动任何线段。
求操作后恰好被 条线段覆盖的非负整数点的最大数量。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例包含两行:
第一行三个整数 。
第二行 个整数 。
输出格式
每个测试用例输出一行一个整数,表示恰好被 条线段覆盖的整数点的最大数量。
数据范围
- ;
- ,;
- ;
- 所有测试用例的 之和不超过 。
样例
输入
3
3 2 1
2 6 2
3 3 2
6 2 0
5 1 3
5 6 7 8 9
输出
6
3
0
样例说明
第一组可以将第三条线段的左端点改成 ,得到三条互不相交的线段,共有 个整数点恰好被覆盖一次。
第二组可以将第一条线段的左端点改成 。