← 返回题目列表

AtCoder · ajo2024_final_a

A. 苹果和盒子

中文机器翻译题面 查看原题

配点 : 1000 点

問題文

在数轴上 N 苹果 有 N 盒子。具体来说,坐标 A_1, \dots, A_N 苹果位于坐标处 B_1, \dots, B_N 处有一个盒子。

负责将苹果装箱的AtCoder先生操作机械臂将苹果装箱。机器人手臂最初位于坐标 它位于 0 ,可以在数轴上自由移动。当机械臂位于苹果坐标处时,可以抓取苹果,当位于盒子坐标处时,可以释放苹果并将其放入盒子中。然而,机械臂一次只能容纳一个苹果,每个盒子只能容纳一个苹果。没有诸如必须将某些苹果放入某个盒子之类的限制。

由于工作时间限制,机械臂行走的总距离为 必须小于或等于 T 。另外,机器人手臂会在工作结束时协调坐标。 您应该回到 0 。这时候,你能在盒子里放多少个苹果?

制約

  • 1 \leq N \leq 4\,500
  • 0 \leq T \leq 10^{14}
  • 1 \leq A_1 < A_2 < \cdots < A_N \leq 10^{10}
  • 1 \leq B_1 < B_2 < \cdots < B_N \leq 10^{10}
  • A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_N 都不同
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N T
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

请打印答案。


入力例 1

3 12
1 2 3
4 5 6

出力例 1

2

如果如下所示移动机器人手臂,2 你可以在盒子里放两个苹果。

  1. 协调机器人手臂 坐标来自 0 移动到 1 并抓住那里的苹果。 移动到
  2. 协调机器人手臂 坐标来自 1 移动到 4 并将苹果放入那里的盒子里。 移至
  3. 协调机器人手臂 坐标来自 4 移动到 3 并抓住那里的苹果。 移动到
  4. 协调机器人手臂 坐标来自 3 移动到 5 并将苹果放入那里的盒子里。 移至
  5. 协调机器人手臂 坐标来自 5 移动到 0 。

要移动的距离是 12 ,因此满足条件。


入力例 2

3 11
1 2 3
4 5 6

出力例 2

1

如果如下所示移动机器人手臂,1 你可以在盒子里放两个苹果。

  1. 协调机器人手臂 坐标来自 0 移动到 2 并抓住那里的苹果。 移动到
  2. 协调机器人手臂 坐标来自 2 移动到 5 并将苹果放入那里的盒子里。 移至
  3. 协调机器人手臂 坐标来自 5 移动到 5.2 。
  4. 协调机器人手臂 坐标来自 5.2 移动到 0 。

要移动的距离是 10.4 ,因此满足条件。


入力例 3

5 18000000000
1000000000 1000000001 1000000002 9999999997 9999999998
5000000000 5000000001 5000000002 9999999999 10000000000

出力例 3

2