Problem1929--Number

1929: Number

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 128 MB

Submit

Description

TC 要前往遥远的意大利,献上厚礼。   

TC 手上有 n 个礼物,每个礼物有一个价值 ai,TC 只能选择连续的若干个礼物。 

为表诚意,TC 所带的礼物的价值总和要大于等于S。运费以礼物个数为计量单位,所以 TC 希望在满足以上条件的情况下,带个数尽量少的礼物。   

TC 想知道最后带的礼物的总数量是多少,你能帮他解决吗? 

Input

输入文件共三行。
第一行输入仅一个正整数 n,意义如题所述
第二行输入 n 个正整数 ai,表示序列中的元素。
第三行输入仅一个正整数 S,意义如题所述。
每两个输入的数之间都用一个空格隔开。 
题目保证:1<=n<=4*106 ,1<=ai<=109,1<=S<=4*1015

Output

输出文件仅一行一个整数,表示最后的总数量。

Sample Input Copy

8
4 12 10 18 17 10 17 17
40

Sample Output Copy

3