提示: 欢迎访问OurACM平台。
Problem 1541 Exploration

Accept: 73    Submit: 208
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Bessie is traveling on a road teeming with interesting landmarks. The road is labeled just like a number line, and Bessie starts at the "origin" (x=0). A total of N (1<=N<=50,000) landmarks are located at points x_1, x_2, ..., x_N (-100,000<=x_i<=100,000). Bessie wants to visit as many landmarks as possible before sundown, which occurs in T (1<=T<=1,000,000,000) minutes. She travels 1 distance unit in 1 minute.

Bessie will visit the landmarks in a particular order. Since the landmarks closer to the origin are more important to Farmer John, she always heads for the unvisited landmark closest to the origin. No two landmarks will be the same distance away from the origin.

Help Bessie determine the maximum number of landmarks she can visit before the day ends.

Input

The input will consist of several datasets.
Each dataset contains two parts:
  *Line 1: Two space-separated integers: T and N.
  *Lines 2..N+1: Line i+1 contains a single integer that is the location of the ith landmark: x_i.
Input is terminated by end of file.

Output

For each dataset,you should output the maximum number of landmarks Bessie can visit in one line.

Sample Input

25 5 10 -3 8 -7 1

Sample Output

4

Hint

Input Details:
Bessie has 25 minutes before sundown, and there are 5 landmarks located at positions 10, -3, 8, -7, and 1.
Output Details:
Bessie sequentially visits the landmarks at locations 1, -3, -7, and 8, after which she has traveled a total of 24 minutes. She cannot visit the next intended landmark at position 10, since this would extend her total travel time to 26 minutes.

Source

USACO 2007 November

Submit  Back  Status  Discuss