#1243. 山屋惊魂

山屋惊魂

题目背景

仔仔在玩一款名叫山屋惊魂的游戏。

题目描述

仔仔在游戏中扮演的角色有一个被称为「神智」的属性,初始时,这一属性为 x0x_0

随着游戏的进行,仔仔依次获得了 nn 件物品,对于第 ii 件物品,只有当人物的神智不低于 aia_i 时才能装备该物品,装备后,人物的神智会增加 bib_i

现在,给出11nn 的物品依次出现的顺序。限制条件是:当获取到物品时,如果满足装备该物品的条件(也就是人物的神智不低于 aia_i),则装备该物品(此时人物的神智会增加 bib_i);否则无法装备该物品,只能选择放弃。

请你求出,仔仔一共装备了几件物品。

输入格式

第一行是两个整数,表示物品数量 nn 和初始的神智 x0x_0。 第二行有 nn 个整数,第 ii 个整数表示装备物品 ii 最少需要的神智值 aia_i。 第三行有 nn 个整数,第 ii 个整数表示装备物品 ii 后增加的神智值 bib_i

输出格式

输出一行一个整数,表示仔仔装备的物品数量。

样例 #1

样例输入 #1

3 1
1 3 2
1 1 1

样例输出 #1

2

提示

样例 1 解释

初始仔仔的精神力为 11。 他获得了第一件物品,装备第一件物品需要的神智不低于 11,符合要求,故他装备了第一件物品,神智增加 11,变成 22。 接着遇到第二件物品,要求神智不低于 33,不符合条件,于是只能放弃。 最后遇到第三件物品,要求神智不低于 22,此时神智是 22,符合要求,故装备该物品,神智增加 11,变成 33。 需要注意的是,虽然此时已经可以装备第二件物品,但是第二件物品已经被放弃了,所以无法再次获得。 最终,仔仔装备了两件物品。

数据规模与约定

  • 对于 10%10\% 的数据,保证 x0<mini=1naix_0 < \min\limits_{i = 1}^n a_i
  • 对于另外 10%10\% 的数据,保证 n=1n = 1
  • 对于另外 20%20\% 的数据,保证 bi=0b_i = 0
  • 对于另外 20%20\% 的数据,保证 ai<ai+1a_i < a_{i + 1}(对 1i<n1 \leq i < n);
  • 对于 100%100\% 的数据,保证 1n1051 \leq n \leq 10^50ai,bi,x01090 \leq a_i, b_i,x_0 \leq 10^9