#3254. 「JOI 2020 Final」集邮比赛 3

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

译自 JOI 2020 Final T3「スタンプラリー 3 / Collecting Stamps 3」。

JOI 君生活的 IOI 国有一个著名的湖泊,今天一场集邮大会在湖边举行。

绕湖一圈总共有 N 种邮票可以收集,编号分别为 1\ldots N ,收集点绕湖顺时针排列。湖的周长为 L ,第 i 张邮票 (1\le i\le N) 的收集点在距离出发点顺时针走 X_i 米的位置。

参赛者在比赛开始的时候要站在出发点的位置,当大会开始时,参赛者可以绕湖顺时针或者逆时针移动,参赛者能够得到第 i 张邮票 (1\le i\le N) 当且仅当他到达收集点的时间在比赛开始时的 T_i 秒以内(含)。

JOI 君也是集邮大会的参与者。他的移动速度是每秒钟 1 米,你可以认为只有移动才会消耗时间。

请你计算他最多能收集到多少种邮票。

输入格式

第一行两个正整数 N, L ,表示邮票种类和湖泊周长。

接下来一行 N 个数,分别为 X_1, X_2, \dots, X_N ,表示各种类邮票的收集位置。

接下来一行 N 个数,分别为 T_1, T_2, \dots, T_N ,表示各种类邮票的最晚可收集时间。

输出格式

输出一行一个整数,表示最多能收集到多少种种类的邮票。

样例

样例输入 1

6 25
3 4 7 17 21 23
11 7 17 10 8 10

样例输出 1

4

样例解释 1

JOI 君可以通过下述策略收集到 4 种邮票:

  1. 逆时针走 2 米,此时只过了 2 秒,可以收集到第 6 种邮票。
  2. 逆时针走 2 米,此时只过了 4 秒,可以收集到第 5 种邮票。
  3. 顺时针走 7 米,此时只过了 11 秒,可以收集到第 1 种邮票。
  4. 顺时针走 1 米,此时已经过了 12 秒,无法收集到第 2 种邮票。
  5. 顺时针走 3 米,此时只过了 15 秒,可以收集到第 3 种邮票。

JOI 君没有办法收集到 5 种或更多邮票,所以答案是 4

样例输入 2

5 20
4 5 8 13 17
18 23 15 7 10

样例输出 2

5

样例输入 3

4 19
3 7 12 14
2 0 5 4

样例输出 3

0

样例输入 4

10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46

样例输出 4

5

数据范围与提示

对于 100\% 的数据,保证 1\le N\le 200, 2\le L\le 10^9, 1\le X_i < L, X_i < X_{i+1}, 0\le T_i \le 10^9

子任务编号 分值 特殊限制
1 5 N\le 12, L\le 200, T_i\le 200
2 10 N\le 15
3 10 L\le 200,T_i\le 200
4 75