Treasure Hunt

There are $N$ people searching for treasure on the segment $[0,L]$. They are numbered $1,2,\cdots,N$ in increasing order of position, and person $i$ is located at coordinate $A_i$.

Each person chooses exactly one direction, left or right, to search. Person $i$ can search up to distance $B_i$ from their position in the chosen direction. However, they cannot leave the segment or search past another person's position.

For convenience, let $A_0=0$ and $A_{N+1}=L$. If person $i$ chooses left, their searched interval is

If person $i$ chooses right, their searched interval is

The region searched by all $N$ people is the union of their searched intervals. Choose a direction for every person to maximize the length of this union, and find that maximum length.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ L$ $A_1\ A_2\ \cdots\ A_N$ $B_1\ B_2\ \cdots\ B_N$

For each test case, print the maximum possible length of the searched region on one line.

• $1 \leq T \leq 20$.
• $1 \leq N \leq 200\,000$.
• $1 \leq L \leq 1\,000\,000\,000$.
• $0 \leq A_i \leq L$ ($1 \leq i \leq N$).
• $A_i < A_{i+1}$ ($1 \leq i < N$).
• $0 \leq B_i \leq 1\,000\,000\,000$ ($1 \leq i \leq N$).
• The sum of $N$ over all test cases does not exceed $200\,000$.