题目描述

這天，小齊與小田各派出 $n$ 隻機器馬進行 $n$ 回一對一的對戰，雙方的出賽順序均已排定且不得再更改。已知對於 $1\le i \le n$，小齊第 $i$ 場出賽的機器馬原始戰力是 $a_i$，小田第 $i$ 場的機器馬原始戰力則是 $b_i$，且 $0\le a_i, b_i< P$，其中 $P$ 是一個給定的正整數。每一場對戰時，戰力高者獲勝。

小田為了贏取更多的勝利，研發出了能調整這些機器馬戰力的燃料，每一種燃料有一個魔力值 $m$，當原始戰力 $b_i$ 的機器馬使用了魔力值 $m$ 的燃料，戰力就會變成 $(b_i + m) \% P$，這裡 $\%$ 表示取餘數的運算。對小田來說，如果每一隻機器馬都可以挑選不同魔力值的燃料，當然就太好了，但是由於某些限制，小田只能生產出最多兩種燃料，且每一隻機器馬都必須使用恰一種燃料才可以。換句話說，小田可以選擇兩個非負整數 $s$ 與 $t$，若 $(b_i + s) \% P > a_i$ 或 $(b_i + t) \% P > a_i$，則小田可以贏得第 $i$ 場比賽的勝利。小田希望能挑選出兩種魔力值，以獲得最多的勝利。請計算並輸出小田的最大勝利場次數。請注意，小田的每一隻機器馬必須使用所生產的兩種燃料之一，即使原先戰力已經勝過對方的機器馬也必須挑選其中之一使用。

舉例來說，假設 $P=10$，小齊與小田的原始戰力如下表。若小田選擇生產魔力值 $s=1$ 與 $t=6$ 的兩種燃料，那麼他可以戰勝 $5$ 場比賽。另，小田沒有戰勝 $6$ 場以上比賽的可能，因此所求答案是 $5$。

$$\begin{array}{|l|l|l|l|l|l|l|l|} \hline \text{小齊戰力 } a_i & 6 & 7 & 9 & 4 & 8 & 5 & 5 \\ \hline \text{小田戰力 } b_i & 3 & 7 & 6 & 9 & 9 & 1 & 5 \\ \hline s=1 \text{ 與 } t=6 & 3 + 6 > 6 & 7 + 1 > 7 & & (9 + 6) \% 10 > 4 & & 1 + 6 > 5 & 5 + 1 > 5 \\ \hline \end{array}$$

输入格式

$n$ $P$
$a_1$ $a_2$ $\ldots$ $a_n$
$b_1$ $b_2$ $\ldots$ $b_n$

• $n$ 代表比賽的回合數，同時也是小齊和小田各自派出的機器馬數量。
• $P$ 代表計算戰力用的參數。
• $a_i$ 代表小齊第 $i$ 場出賽的機器馬原始戰力。
• $b_i$ 代表小田第 $i$ 場出賽的機器馬原始戰力。

输出格式

$\textrm{ans}$

• $\textrm{ans}$ 代表小田的最大勝利場次數。

5 6
3 1 5 3 4
0 2 3 4 0

4

7 10
6 7 9 4 8 5 5
3 7 6 9 9 1 5

5

提示

測資限制

• $1 \le n \le 2\times 10^5$。
• $1 \le P \le 10^9$。
• $0 \le a_i < P$。
• $0 \le b_i < P$。
• 輸入的數皆為整數。

評分說明

本題共有五組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。

子任務	分數	額外輸入限制
1	$5$	$n \le 100, P \le 100$
2	$7$	$n \le 100, P \le 10000$
3	$17$	$n \le 5000$
4	$40$	對於所有 $i$，$b_i \le a_i$
5	$31$	無額外限制