#P3086. [JOI 2020 Final] スタンプラリー 3

[JOI 2020 Final] スタンプラリー 3

题目描述

给定一个周长为 LL 的圆,从一个点出发,有 NN 个黑白熊雕像,编号为 11NN,第 ii 个雕像在顺时针 XiX_i 米处,如果你没有在 TiT_i 秒内收集到这个黑白熊雕像,那么这个雕像就会发出“唔噗噗噗”的声音然后爆炸。

现在 JOI 君在这个点,他每一秒可以移动一米,并且他可以顺时针或者逆时针的移动。

JOI 君想问,他最多能收集到多少个黑白熊雕像?

输入格式

第一行两个整数 N,LN,L 代表雕像数和圆的周长。
第二行 NN 个整数 XiX_i 代表每个雕像在顺时针多少米处。
第三行 NN 个整数 TiT_i 代表每个雕像需要在多少秒内拿到。

输出格式

一行一个整数代表答案。

6 25
3 4 7 17 21 23
11 7 17 10 8 10
4
5 20
4 5 8 13 17
18 23 15 7 10

5
4 19
3 7 12 14
2 0 5 4

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

5

提示

样例 1 解释

JOI 君可以按照如下策略拿到 44 个黑白熊雕像:

方向 路程 总时间 第几个雕像 能否拿到
逆时针 22 22 66 \sqrt{}
44 55
顺时针 77 1111 11
11 1212 22 ×\times
33 1515 33 \sqrt{}

样例 2 解释

JOI 君可以直接一直逆时针走。

样例 3 解释

JOI 君无法得到任何一个雕像。

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(5 pts):N12N \le 12L200L \le 200Xi200X_i \le 200
  • Subtask 2(10 pts):N15N \le 15
  • Subtask 3(10 pts):L200L \le 200Ti200T_i \le 200
  • Subtaks 4(75 pts):无特殊限制。

对于 100%100\% 的数据:

  • 1N2001 \le N \le 200
  • 2L1092 \le L \le 10^9
  • 1Xi<L1 \le X_i<L
  • Xi<Xi+1X_i < X_{i+1}
  • 0Ti1090 \le T_i \le 10^9

说明

翻译自 第19回日本情報オリンピック 本選 C スタンプラリー 3