#P18544. China Convex Polygon Contest

China Convex Polygon Contest

China Convex Polygon Contest

Kevin 和小青鱼(Little Cyan Fish)参加了中国凸多边形竞赛决赛(China Convex Polygon Competition Final,简称 CCPC Final)。

在线评测系统有一项名为 Last Success 的统计,表示当前最后一个成功解决题目的人是谁。

比赛持续 mm 秒,共有 nn 道题。小青鱼获知,Kevin 会分别在比赛开始后的第 a1,a2,…,ana_1,a_2,\ldots,a_n 秒成功解决一道题。而小青鱼完成各道题目分别需要 b1,b2,…,bnb_1,b_2,\ldots,b_n 秒。

小青鱼希望安排自己的策略,即做题顺序以及各题提交的时刻,使 Last Success 属于自己的总时长最大。

请注意:

  • 完成一道题之后,小青鱼不必立刻提交。他可以先继续做其他题目。
  • 提交和其他操作不消耗时间,因此小青鱼可以在做另一道题的过程中提交已经完成的题目。
  • 如果小青鱼和 Kevin 在同一时刻提交,Last Success 归小青鱼。
  • 比赛刚开始且尚未有任何提交时,Last Success 为空。

输入格式

第一行包含整数 TT(1≤T≤1051\le T\le10^5),表示测试用例数。

对于每个测试用例:

  • 第一行包含两个整数 n,mn,m(1≤n≤1051\le n\le10^5,1≤m≤1091\le m\le10^9)。
  • 第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n(1≤ai≤m1\le a_i\le m),保证 ai<ai+1a_i<a_{i+1}。
  • 第三行包含 nn 个整数 b1,…,bnb_1,\ldots,b_n(1≤bi≤m1\le b_i\le m)。

保证一个输入文件内所有测试用例的 nn 之和不超过 10510^5。

输出格式

对每个测试用例输出一行,一个整数,表示 Last Success 属于小青鱼的最大总时长。

原样例

3
3 10
1 5 9
1 2 3
3 10
1 5 9
1 1 4
3 10
1 5 9
1 5 10
9
9
7

原样例说明

对于第一个测试用例,小青鱼可以:

  • 从第 00 秒开始做第一题,在第 11 秒完成并立刻提交;
  • 从第 11 秒开始做第二题,在第 33 秒完成,等到第 55 秒提交;
  • 从第 44 秒开始做第三题,在第 77 秒完成,等到第 99 秒提交。

从第 11 秒起,Last Success 始终属于小青鱼,因此答案是 10−1=910-1=9。

对于第三个测试用例,小青鱼可以:

  • 从第 00 秒开始做第一题,在第 11 秒完成并立刻提交;
  • 从第 11 秒开始做第二题,在第 66 秒完成并立刻提交;
  • 放弃无法在比赛内完成的第三题。

从第 11 秒到第 55 秒,以及从第 66 秒到第 99 秒,Last Success 属于小青鱼,因此答案是 (5−1)+(9−6)=7(5-1)+(9-6)=7。