Description

The Ironman Duathlon is a traditional sports event of Jilin Institute of Education. The race consists of long-distance running and cycling. Each contestant must first complete a $k$-kilometer run, and then complete an $r$-kilometer bike ride to reach the finish line. Different contestants are good at different events: some are better at running, while others are better at cycling. If the total distance $s=k+r$ is fixed, then the larger $k$ is, the more advantageous it is for contestants who are good at running; the smaller $k$ is, the more advantageous it is for contestants who are good at cycling.

Now you are given the total distance $s$, as well as each contestant’s average speed for running and cycling. Please find the values of $k$ and $r$ that are the most favorable for a specified contestant. “Most favorable” means that after choosing this $k$ and $r$, the contestant can win the championship, and the lead over the second place is as large as possible.

Input Format

Your program reads input from a file.
The first line contains two positive integers $s$ and $n$. $s$ is the total distance (in kilometers, $s\leq 2^{31}$), and $n$ is the total number of contestants ($2\leq n\leq 100$).
The next $n$ lines each contain two real numbers, representing each contestant’s average running speed and average cycling speed (in kilometers per hour).
The $n$-th contestant is the specified contestant. Your task is to find the most favorable $k$ and $r$ for them.

Output Format

Your program should output three numbers $k,r,t$, representing the most favorable $k$ and $r$ for contestant $n$ (floating-point numbers, rounded to $2$ decimal places), and the maximum number of seconds by which contestant $n$ can lead the second place under this choice of $k$ and $r$ (rounded to an integer). If another contestant ties with them for first place, then $t=0$. If contestant $n$ cannot win no matter what $k$ and $r$ are chosen, output NO.

100 3
10.0 40.0
20.0 30.0
15.0 35.0

14.29 85.71 612

Hint

Translated by ChatGPT 5