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$ | 无额外限制 |