AT_abc467_e [ABC467E] Adjacent Sums (hard)

**The problem statement of Problem E is the same as Problem C. Only the constraint shown in red differ.** You are given integer sequences $ A=(A_1,A_2,\dots,A_N) $ and $ B=(B_1,B_2,\dots,B_{N-1}) $ consisting of integers between $ 0 $ and $ M-1 $ , inclusive. The lengths of $ A $ and $ B $ are $ N $ and $ N-1 $ , respectively. You can perform the following operation on $ A $ any number of times. - Choose an integer $ i $ with $ 1 \leq i \leq N $ , and add $ 1 $ to $ A_i $ . Find the minimum number of operations required to satisfy the following condition. It can be proved that the condition can always be satisfied under the constraints of this problem. - For $ i=1,2,\dots,N-1 $ , the remainder when $ A_i+A_{i+1} $ is divided by $ M $ equals $ B_i $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_{N-1} $

Output the answer on one line.

### Sample Explanation 1 If we choose $ i=2 $ for the first operation, we get $ A=(4,7,7) $ . If we choose $ i=1 $ for the second operation, we get $ A=(5,7,7) $ . If we choose $ i=1 $ for the third operation, we get $ A=(6,7,7) $ . If we choose $ i=2 $ for the fourth operation, we get $ A=(6,8,7) $ . If we choose $ i=1 $ for the fifth operation, we get $ A=(7,8,7) $ . Since $ A_1+A_2=7+8=15 $ and $ A_2+A_3=8+7=15 $ , the condition is satisfied. The condition cannot be satisfied with four or fewer operations, so the answer is $ 5 $ . ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $\red{3 \leq M \leq 10^9}$ - $ 0 \leq A_i \leq M-1 $ - $ 0 \leq B_i \leq M-1 $ - All input values are integers.