分数: 233 分
问题陈述
高桥正在玩 RPG 游戏。
在这个游戏中,有一个地牢,包括 N 房间排列成一排。房间有编号 1, 2, \ldots, N 从入口到后面,每个房间都有一只怪物在里面等待。房间里的怪物实力 i (1 \leq i \leq N) is V_i.
高桥控制着一条初始强度为 W 征服这个地牢。史莱姆按照从房间开始的顺序访问每个房间一次 1 到房间 N,按顺序访问它们 1, 2, \ldots, N。它不能返回或跳过房间。
史莱姆访问房间时的“当前强度”被定义为初始强度 W 加上访问该房间之前吸收的所有怪物的总力量。
当史莱姆来到房间时 i,恰好发生以下两种情况之一:
- 如果怪物的力量 V_i is 小于或等于 史莱姆的当前强度(包括以下情况) V_i 等于史莱姆当前的强度),史莱姆吸收怪物。 V_i 立即添加到史莱姆的强度中,添加后的值成为后续房间的当前强度。
- 如果怪物的力量 V_i is 严格大于 史莱姆当前的强度,史莱姆无法吸收怪物,并且史莱姆的强度不会改变。
找出史莱姆访问过所有房间后的强度 1 到房间 N 按顺序。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W \leq 10^9
- 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
- 所有输入值均为整数。
- 保证答案小于 2^{63} (它适合签名的 64位整数)。但是,它可能超出签名的范围 32位整数 (2^{31}-1 或更少)。
输入
N W V_1 V_2 \cdots V_N
- 第一行包含一个整数 N 代表房间数和一个整数 W 代表史莱姆的初始强度,以空格分隔。
- 第二行包含整数 V_1, V_2, \ldots, V_N 代表每个房间中怪物的强度,以空格分隔。
输出
在单行上以整数形式输出征服地牢后史莱姆的强度。
示例输入 1
5 3 2 4 1 3 7
示例输出 1
20
示例输入 2
8 5 3 6 2 10 4 8 1 20
示例输出 2
59
示例输入 3
10 1 1 3 2 5 100 4 6 3 2 1000000000
示例输出 3
19