Travel Guide

Yoonhwa is a travel guide who leads tourists on a bus. One day, she is guiding $N$ tourists.

During a one-hour lunch break, each tourist goes wherever they want. At the end of the break, no tourist has returned to the bus. Yoonhwa starts from the bus, must meet every tourist, tell them to return immediately, and then return to the bus herself.

At time $t = 0$, the bus is at the origin $(0, 0)$. Each tourist keeps moving in a straight line from their current position with their own speed and direction. When Yoonhwa meets a tourist, that tourist immediately changes direction and moves straight back to the bus at the same speed.

Find the minimum possible time at which everyone, including Yoonhwa, has arrived back at the bus.

The first line contains the number of tourists $N$ $(1 \le N \le 8)$.

The second line contains Yoonhwa's speed as a decimal number.

Each of the next $N$ lines contains four decimal numbers $x_i$, $y_i$, $v_i$, and $a_i$.

• $(x_i, y_i)$ is the position of the $i$-th tourist at time $t = 0$ $(-10^6 \le x_i, y_i \le 10^6)$.
• $v_i$ is that tourist's speed $(1 \le v_i \le 100)$.
• $a_i$ is that tourist's movement direction in radians $(1 \le a_i \le 2\pi)$, measured counterclockwise from the positive $x$-axis.

Print the minimum time, rounded to the nearest integer.

The answer is guaranteed to be at most $10^6$.