War - Declaration of War

Time limit2sMemory limit128 MB

Summary

Given people's positions and speeds plus blocking line-segment obstacles, find the shortest obstacle-avoiding path to the border for each and output the maximum travel time.

Level: Hard8 of 10
Topics: Geometry, Shortest path, Graph, Math
Solved: No attempts yet

Problem

You and the king of the neighboring country have become so angry with each other that both sides are preparing for war.

Before declaring war, you want all of your people currently in the neighboring country to return to your own country. On year Y, month M, day D, every person starts moving toward the border at the same time, following the return order that had already been delivered.

The neighboring country contains impassable straight-line obstacles, so reaching the border may take longer.

If every person always takes a fastest possible route to cross the border, compute the minimum time after which everyone has crossed it.

Input

The first line contains the number of people N (1 ≤ N ≤ 50) and the number of straight-line obstacles M (1 ≤ M ≤ 50).

Each of the next N lines contains one person's coordinates (x, y) and speed v. These values are integers, with 1 ≤ x, y ≤ 100 and 1 ≤ v ≤ 10.

Each of the following M lines contains the two endpoints of one straight-line obstacle in the form (x1, y1) - (x2, y2). The obstacle coordinates are integers, with 0 ≤ x1, x2 ≤ 100 and 1 ≤ y1, y2 ≤ 100.

No two straight-line obstacles intersect. The line y = 0 is the border.

Moving a distance a at speed v takes time a / v.

Output

Print the minimum time needed for every person to cross the border, rounded to one digit after the decimal point.

Examples1

Example 1

Input

3 3
(2,7) 1
(4,7) 2
(8,4) 1
(0,1) - (4,2)
(5,3) - (7,2)
(3,5) - (6,5)

Expected output

7.3