P11910 [NHSPC 2023] I. 對戰機器馬

這天，小齊與小田各派出 $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}$ 代表小田的最大勝利場次數。

### 測資限制 * $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$ | 無額外限制 |