Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Exploration
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 5112Accepted: 2444

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 x1, x2, ..., xN (-100,000 ≤ xi ≤ 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

* 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: xi

Output

* Line 1: The maximum number of landmarks Bessie can visit.

Sample Input

25 5
10
-3
8
-7
1

Sample Output

4

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator