D. 非暴力不合作(特别弱化版)

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

「手段的不纯洁必然导致目的的不纯洁。」
——莫罕达斯·卡拉姆昌德·甘地

在第一次世界大战结束之后,英国对印度的统治日趋严苛,独立呼声此起彼伏。在这一背景下,甘地领导了印度自治同盟的政治运动,提出非暴力不合作的政治主张,并多次以绝食作为政治武器对抗英属印度当局。

甘地是使用绝食进行政治抗议的第一人。而既然是政治抗议,那目标自然不是死亡而是实现政治诉求。因此在绝食的流程中,绝食者在需要保障自己的生命的同时达到最大的抗议效果。

假设在 天政治抗议的过程中,绝食者具有一个状态 (其值初始为 ),并同样有 个食物,从 到 编号,第 天食物的权值是 ,同时,还给出每一天绝食的困难度,第 天绝食的困难度是 。

在绝食抗议的第 天,绝食者可以选择:

  • 吃食物,这会使得绝食者在当天结束时状态增加 ,
  • 不吃食物,这会使得绝食者在当天结束时状态减少 。

必须保证绝食者在任何时候(从第 天到第 天结束)的状态值 ,否则绝食者有死亡的风险。

请问绝食者如何在满足以上条件的前提下,选择「不吃食物」的天数最多?若绝食者无法在保证没有死亡风险的情况下完成抗议活动,则抗议失败。

输入格式

输入共 行,第一行 个整数 。

第二行 个整数 ,表示食物的权值。

第三行 个整数 ,表示每天的困难度。

输出格式

一行一个整数,表示绝食者在满足条件的前提下,选择「不吃食物」最多的天数。若抗议活动失败,则输出 。

样例

输入样例1

83 11 5
13 10 3 27 31 
36 40 23 32 46 

输出样例1

3

输入样例2

50 16 7
37 13 5 53 5 56 7 
65 78 89 11 26 43 9 

输出样例2

4

数据范围与提示

对于所有数据,保证 。