【UR #34】货物运输
Good Luck.
跳蚤国的一批货物运到了城墙顶端，原计划是使用货物数量个吊机将货物从顶端运输到底端，但是现在经费不够了。计划已经执行了一段时间，请你挽救这个项目。
祝你好运。
有一面垂直于地平面的矩形城墙，宽为 $N$，高为 $H$，不计厚度，底边即为墙面与地平面的交线。以墙面左下角为原点，底边为横轴，过原点的地平面的法线为纵轴建立平面直角坐标系，即纵轴表示高度。
平面上有 $N$ 个可忽略形状与大小的平台，第 $i$ 个初始位于 $(i,h_i),1 \le h_i \le H$，任意时刻你可以花费 $1$ 的代价让 $h_i$ 减一，但需要保证 $h_i$ 始终非负，此时在平台 $i$ 上的所有货物的高度将会同步减一。每个平台上可承载无数的货物，初始第 $i$ 个平台上有货物编号为 $i$，抗摔度 $k_i$。
任意时刻，当货物 $i$ 位于 $(x_i,y_i)$ 时，你可以让工作人员将它扔到 $(x'_i,y_i),x'_i \in \{x_i-1,x_i+1\}$，然后它会做自由落体运动。设当前平台 $x'_i$ 存在且位于 $(x'_i,h_{x'_i})$，此时如果有 $h_{x'_i} \le y_i$ 货物会落到高度 $d=h_{x'_i}$，否则货物会落到高度 $d=0$，如果 $y_i-d>k_i$ 则货物会损坏。
特别地，货物可以直接从 $(x_i,y_i)$ 被扔到 $(x_i,0)$，如果 $y_i>k_i$ 则货物会损坏。
请你合理安排操作使得所有货物到达高度 $d=0$ 并使得不存在货物损坏，在此前提下最小化代价。
输入格式
本题单个测试点有多组测试数据。
第一行一个正整数 $T$ 表示数据组数。
接下来，对于每组数据有：
第一行两个正整数 $N,H$。
第二行 $N$ 个正整数，第 $i$ 个表示 $h_i$。
第三行 $N$ 个整数，第 $i$ 个表示 $k_i$。
输出格式
共输出 $T$ 行，对于每组数据，输出一行一个整数表示最小代价。
3
4 4
1 2 4 3
4 4 1 4
1 10
10
3
4 1000000000
500000000 1000000000 500000000 1000000000
1 1 1 1
1
7
1499999998
样例一第一组数据操作依次如下：
对于 $k_i=H$ 的货物 $i$ 可以忽略，因为它们可以随时被扔到高度 $0$ 而不产生损坏，于是此处只用考虑货物 $3$。
- 将第三个平台高度下降到 $3$，代价加一。
- 货物 $3$ 从三号平台被扔到二号平台，高度差 $3-2=1\le k_3$，货物没有损坏。
- 货物 $3$ 从二号平台被扔到一号平台，高度差 $2-1=1\le k_3$，货物没有损坏。
- 所有货物从当前所在平台直接扔到高度 $0$，没有损坏。
总代价为一。
3
8 8
2 8 7 7 7 2 4 3
8 8 8 8 1 8 8 8
8 8
5 7 8 6 7 3 5 6
8 8 8 2 8 8 8 8
8 8
8 3 2 1 6 7 1 3
3 8 8 8 8 8 8 8
5
3
2
4
3 5
4 2 5
1 5 2
6 4
1 2 2 2 4 2
2 4 1 4 3 1
8 8
7 5 4 2 7 8 3 3
8 1 8 2 8 1 3 4
8 8
8 7 6 8 8 7 3 8
3 1 1 1 7 1 2 6
3
1
6
8
4
6 10
5 4 2 10 9 6
1 10 10 2 10 10
10 4
1 3 1 2 4 4 2 1 1 2
4 3 1 4 3 1 3 3 2 3
10 998244353
1234567 7654321 13579 24680 114514 1919810 2333333 31415926 5358 415411018
998244353 98244353 8244353 244353 44353 4353 353 53 3 1
20 1000000000
938907742 231010604 158201401 555669490 773977387 990658257 514866633 239695215 494763446 509916726 199234105 624265577 840630759 505243719 79024890 815192346 809962669 278340663 833067885 564824242
756301351 614733845 376221000 777115729 423316637 17942484 923266431 620274723 399632356 75933326 189624037 566622731 18161401 279015262 98423791 317582345 33871998 45102181 951005029 184798288
7
1
446826624
3023869941
数据范围
本题采用捆绑测试。
设 $\sum N$ 为单个测试点内所有 $N$ 的和。
对于 $100\%$ 的数据，保证：
- $1 \le N,T \le 3 \times 10^5,1 \le \sum N \le 6 \times 10^5,1 \le k_i,h_i \le H \le 10^{12}$。
| 子任务编号 | 分值 | $N \le$ | $\sum N \le$ | $H \le$ | 特殊性质 |
|---|---|---|---|---|---|
| $1$ | $5$ | $8$ | $100$ | $8$ | A |
| $2$ | $5$ | $3 \times 10^5$ | $6 \times 10^5$ | $10^{12}$ | |
| $3$ | $10$ | $500$ | $2000$ | B | |
| $4$ | $5$ | $5000$ | $2 \times 10^4$ | ||
| $5$ | $10$ | 无 | |||
| $6$ | $25$ | $3 \times 10^5$ | $6 \times 10^5$ | B | |
| $7$ | $20$ | C | |||
| $8$ | $20$ | 无 |
特殊性质 A：保证存在且只存在一个 $k_i \not= H$。
特殊性质 B：$k_i$ 全部相等。
特殊性质 C：$k_i$ 的生成方式为：选定一个阈值 $K\in [1,H]$，然后每个 $k_i$ 在 $[1,K]$ 中随机生成。
时间限制：$\texttt{5s}$
空间限制：$\texttt{2GB}$