Flowers instead of a tree

Time limit1sMemory limit128 MB

Summary

Choose the vase whose solid-of-revolution volume is closest to the target volume.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Sunyoung's second anniversary with her boyfriend is close. She wants to give him something special. He likes trees a lot, but Sunyoung thinks a tree is too big to hand over as a gift, so she settled on flowers.

Sunyoung believes that every flower has one vase volume that suits it best. She opened an online store to buy a vase, and each listing carries a photo and an outline function. Write a program that finds the vase closest to the volume she wants.

The outline of a vase is the function $f(x) = a e^{-x^2} + b \sqrt{x}$ . Here $x$ is the vertical distance measured from the bottom of the vase, and the vase is the solid obtained by rotating this curve around the $x$ axis. The height of the vase is $h$ , so its volume is

$V = \pi \int_0^h f(x)^2 \, dx$

Two different vases differ in volume by at least $10^{-4}$ . The gap to the volume Sunyoung wants also differs from vase to vase by at least $10^{-4}$ , so exactly one vase is the answer.

Input

The first line contains the volume $V$ that Sunyoung wants and the number of vases $N$ listed in the store. ( $1 < V \le 10^5$ , $0 < N \le 5$ )

Each of the next $N$ lines contains $a$ , $b$ , and $h$ , which determine the outline function of one vase. ( $1 \le a, b, h \le 10$ )

$V$ , $a$ , $b$ , and $h$ are real numbers and are sometimes written without a decimal point.

A vase with $a = 1$ , $b = 2$ , $h = 2$ has volume 34.72348, and a vase with $a = 2$ , $b = 1$ , $h = 2$ has volume 21.77966.

Output

Print the index of the vase whose volume differs least from the volume Sunyoung wants. The first vase has index 0.

Examples1

Example 1
Input
```
25.0 2
1.0 2.0 2.0
2.0 1.0 2.0
```
Expected output
```
1
```