I :: Space Jam

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Michael Jordan is recruited by Loony Tunes characters as the coach and the captain of their basketball team for their important upcoming game against the Nerdlucks. In order to prepare them for their roles, Michael designed sophisticated practices specialized for each of team members. Road-runner, as a member of the team, is given a very strange exercise: It starts when some basketballs are thrown in arbitrary directions on several points of the playground. As the practice starts, Road-runner, initially standing by the basket, must run into each of the balls and hit the ball such that it changes its direction and falls in the basket. Note that Road-runner cannot change the speed of the balls and a ball will not fall in the basket unless it is explicitly hit by Road-runner. The practice ends when the last ball falls into the basket. Road-runner should minimize the total time of the practice. Obviously, the speed of Road-runner is strictly more than any of the balls. You can assume that the balls always move in straight lines and with constant speeds, and their moves will not be affected by the other balls, and it takes no time for Road-runner to hit them. Given the speed of Road-runner and the information of the balls, you have to find the minimum time needed to finish the exercise.

http://sharecode.ir/assets/problem_images/2008_5a49c6292df95fbfd0c67528b41858a0.jpg

Input

The input contains several test cases. Each test case starts with a single integer N (1 <= N <= 8), the number of the balls thrown in the exercise, followed by a line with a single real number R (1 < R <= 100), the maximum speed of Road-runner. Then, there are N lines each with four space-separated real numbers Xi, Yi, Vi, and Di which characterize a basketball. Coordinate numbers Xi and Yi denote the initial position of the ball in the playground (-106 <= Xi, Yi <= 106), Vi shows the constant speed of the ball (1 <= Vi < R), and Di specifies the direction of the ball as the positive angle it makes with X-axis in radians (0 <= Di < 2π). All real numbers in the input are given in standard decimal format with at most 10 digits. By convention, the basket (and thus, the initial position of Road-runner) is assumed to be on the origin. The input ends with a line containing a single 0 which should not be processed as a test case.

Output

For each test case, write a line containing a single integer T which is the minimum time needed to finish the exercise, rounded to the nearest integer. You can assume that T will never exceed 106.

Sample Input

3
200.0
80.0 50.0 40.0 5.95
-370.0 390.0 12.0 2.35
60.0 -160.0 46.0 2.76
1
10.0
25.0 35.0 5.0 1.96
0

Sample Output

51
20
Submit

Source: 9th Iran Nationwide Internet Contest