A. 非暴力不合作(超级弱化版)

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

题目描述

「后世很难想象这世界上曾经走过这样一位血肉之躯。」
——阿尔伯特·爱因斯坦

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

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

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

在绝食抗议的任何一天,绝食者可以选择:

  • 吃还未吃的编号最小的食物,假设其编号为 ,这会使得绝食者在当天结束时状态增加 ,由于体力消耗,绝食者状态会再减少 ,注意绝食者每天最多吃一个食物。
  • 不吃食物,这会使得绝食者在当天结束时状态减少 。

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

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

输入格式

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

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

输出格式

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

样例

样例输入 1

37 5 19 5
3 25 2 28 9 

样例输出 1

3

样例输入 2

31 5 19 9
2 23 12 17 9 0 10 7 4 

样例输出 2

6

数据范围与提示

对于所有数据,满足 ,。

数据保证 。也就是绝食者在第一天开始时没有死亡危险。