← 返回题目列表

AtCoder · awc0039_c

C. 整理书架

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

分数: 366 分

问题陈述

高桥正在整理家里的书架。书架上有 N 书籍排成一排,编号 1, 2, \ldots, N 从左到右。预订 i 的满意度值为 A_i 和重量 B_i.

高桥想要选择 一本或多本连续的书 将 从书架上移到新书架上。具体来说,他选择整数 l, r (1 \leq l \leq r \leq N)并取出所有书籍 l, l+1, \ldots, r.

但是,高桥一次可以搬运的重量是有限制的,因此所选区间内的书籍总重量必须最多为 K。也就是说,必须满足以下条件:

B_l + B_{l+1} + \cdots + B_r \leq K

在所有选择中 l, r 满足这个条件,找到总满意度的最大值 A_l + A_{l+1} + \cdots + A_r.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{15}
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入值均为整数
  • 至少存在一个区间 (l, r) (1 \leq l \leq r \leq N) 使得总重量最多为 K

输入

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
  • 第一行包含一个整数 N 代表书籍数量和一个整数 K 代表重量限制,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每本书的满意度值,以空格分隔。
  • 第三行包含整数 B_1, B_2, \ldots, B_N 代表每本书的重量,以空格分隔。

输出

在选择总权重最大的连续区间时,一行打印最大总满意度 K.


示例输入 1

5 10
3 5 2 8 1
4 3 2 5 6

示例输出 1

15

示例输入 2

8 20
1 4 6 2 10 3 7 5
5 3 4 8 6 2 3 9

示例输出 2

25

示例输入 3

10 1000000000000000
100 200 300 400 500 600 700 800 900 1000
1 1 1 1 1 1 1 1 1 1

示例输出 3

5500