Duathlon

Interview

Time limit1sMemory limit128 MB

Summary

Given each competitor's running and cycling speeds and a fixed total distance, choose the run and cycle legs so the last competitor wins by the largest margin, or report that no such split exists.

Level: Medium6 of 10
Topics: Geometry, Math, Brute force, Implementation
Solved: No attempts yet

Problem

A duathlon is a race in which each competitor first runs $r$ km and then cycles $k$ km. $n$ competitors have entered, and every competitor has a different running speed and cycling speed. One of them has bribed the organizers so that they will choose $r$ and $k$ (with the total distance fixed) to let him win by the largest possible margin. Determine whether this is possible and, if so, find the values of $r$ and $k$ .

Input

The first line contains an integer $t$ , the total distance of the race in km, so that $r + k = t$ . The second line contains an integer $n$ , the number of competitors. Each of the next $n$ lines contains two real numbers: the running speed and cycling speed (in km/h) of one competitor. The last of these $n$ lines is the competitor who bribed the organizers (the cheater); the other $n-1$ are the honest competitors he must beat. You may assume $t$ does not exceed $100$ km and $n$ does not exceed $20$ .

Output

If the race can be fixed as described, print a single line of exactly the form The cheater can win by <S> seconds with r = <R>km and k = <K>km., where <S> is the winning margin in seconds rounded to the nearest whole second and <R> and <K> are the running and cycling distances in km rounded to two decimal places (there is no space between a number and km). If it is not possible for the cheater to win, print The cheater cannot win..

Examples2

Example 1

Input

Expected output

The cheater can win by 612 seconds with r = 14.29km and k = 85.71km.

Example 2

Input

Expected output

The cheater cannot win.