Platform

Time Limit: 1 Second    Memory Limit: 32768 KB

A huge circular platform with radius r was built recently to provide tourists with a better view of the lake beside it. Due to a design defect, the platform has only one entrance and one exit. It often gets quite crouded as many tourists are quite impressed by the beautiful scenery and take photos. Walking across the platfrom is often quite an uneasy task because when others are taking photos, you can't just simply walk in front of them and have to wait until they put down their cameras.

A tourist (let's just call him Tom) has just entered the platform and notices that many photographers are taking photos for tourists. He hates crowded place and wishes to leave as soon as possible. You should help him.

The platform of radius r is placed with its center at (0, 0). It's entrance is at (0, -r) while the exit at (0, r). All photographers and tourists are inside or on the border of the platform. Each photographer is taking a photo for exactly one tourist. Tom may never walk between a photographer and the corresponding tourist, nor could he walk behind that tourist, as shown below.

Input

The input has several cases. Each case begins with r and n, the number of photographers (n <= 1000). n lines follow, each contains 4 real numbers followed by an integer. The first two real numbers are the coordinates of the photographer. The next two numbers are the coordinates of the corresponding tourist. The integer is the time that they finish taking photos. Time starts form 0. Input is terminated by EOF.

Output

For each test case, output a line with the minimal time Tom has to wait.

Sample Input

10 2
0 0 1 0 1
1 -1 0 1 2

Sample Output

1

Submit

Source: Zhejiang University 2003 Summer Camp Qualification Contest