Vasya is stuck in a labyrinth. The labyrinth is a non-self-intersecting polygon with N vertices and sides parallel to the coordinate axes. In the evening Vasya has a programming practice, so he wants to escape from the labyrinth as quickly as possible. He is at the point (Xs, Ys) inside the labyrinth, and the exit is at the point (Xe, Ye). For simplicity, let us represent Vasya as a square with side of A units. The sides of the square are always parallel to the axes. Vasya is considered to have escaped when his center reaches the exit point. Find the minimal escape time. Vasya's speed is V units/sec. If Vasya cannot escape, output -1.
The first line holds two real numbers Xs and Ys (0 ≤ Xs, Ys ≤ 100). The next line holds two real numbers Xe and Ye (0 ≤ Xe, Ye ≤ 100). The following two lines hold real numbers A and V (0.5 ≤ A, V ≤ 10), respectively. The following lines describe the polygon: a single integer N (1 ≤ N ≤ 100) on a line by itself, and each of the following N lines holds a pair of real numbers, Xi and Yi being the coordinates of a vertex (0 ≤ Xi, Yi ≤ 100). All the reals are guaranteed to give an integer when multiplied by 2.
Output the answer on a single line. Your answer will be considered correct if its relative error does not exceed 10 - 6.
Points for all the tests are awarded independently.
1.5 4.5
4.5 1.5
1
1
6
0 0
0 6
3 6
3 3
6 3
6 0
4.472135955
The planet Liberloun has N communication stations, some of which have retranslators around them. At a certain initial moment, a talented astronomer Aytal from Earth sends a message signal to each of the comm stations, which reaches them instantaneously, but with some loss and scatter. It is known that each retranslator receives a fraction p of the initial message (the more retranslators there are, the greater portion of the signal goes to them). Also, a fraction q of the signal is lost. It takes takes 3 hours for a retranslator to forward the message to its comm station. Aytal's computer only retransmits the lost part of the message after 10 hours. The station receives a readable message if the combined fraction of the message that reaches it is no less than S.
Aytal asks you to count how many stations will receive a readable message after H hours.
The first line of input contains an integer N (1 ≤ N ≤ 106) and real numbers p, q (0 ≤ p, q ≤ 1), the number of stations and the fractions, respectively. The second line holds N integers a1, a2, ..., an, where ai is the number of retranslators around the ith comm station (0 ≤ ai ≤ 106). The third line contains two real numbers H, S (0 ≤ H ≤ 1000, 0 ≤ S ≤ 1).
It is guaranteed that for all i the condition p × ai + q ≤ 1 is satisfied.
Output a single integer, the number of stations that will receive a readable message after H hours.
Solutions that fail the tests in the examples will be awarded 0 points and not be further tested.
Each test is scored separately.
2 0.01 0.5
0 1
0 0.5
1
4 0.2 0.2
0 1 2 3
8 0.3
4
In the first example the first station immediately receives half of the message, and the second station 0.49 of the message. Only the first station receives a readable message.
In the second example, after 3 hours the stations number 2, 3, and 4 will receive messages from their retranslators, so all of the stations will receive 0.8 of the message.
It is known that in the Land of Fools there are two types of currency: golden and wooden. There are coins with the values of a1, a2, …, aK wooden units and a golden coin. By the order of wise Buratino, the ruler of the Land of Fools, the monetary system of the country is organized in such a way that any amount from 1 up to M of wooden money can be paid using no more than N coins. Define the minimal and maximal amount of wooden money that the golden coin can be worth. In the case when one golden coin is equal to exactly one number of wooden units, print it as both minimal and maximal.
It is guaranteed that the order of Buratino is fulfilled and one golden coin is not worth more than M wooden units.
First line contains three numbers K, M and N (1 ≤ K ≤ 500, 1 ≤ M, N ≤ 2000). Second line contains K integers a1, a2, …, aK (1 ≤ ai ≤ 500).
Output two space separated integers, the minimal and maximal wooden value of the golden coin.
Solutions that fail the tests in the examples will be awarded 0 points and not be further tested.
Each test is scored separately.
3 10 2
1 2 3
7 7
3 15 3
1 2 5
4 13
Grisha, a young coder, goes shopping for groceries every Saturday. This time he has decided to minimize his spending.
Grisha's town has N grocery shops, and for convenience he has numbered them from 1 to N. Some shops are connected with minibus routes, and the cost of the minibus from the ith shop to the jth one is pij rubles.
There are K different kinds of groceries. The shops stock limited amount of each. Grisha also knows the price for each kind of groceries in each shop. The prices in the shops may differ.
Grisha lives near the shop number 1, so he spends nothing to get there. He may finish his shopping in any of the N shops. Assume that the return home will also cost him nothing.
Given a shopping list, determine the minimum necessary amount of money that Grisha will have to take with him.
The first line of the input contains a single integer N (1 ≤ N ≤ 17), the number of shops.
The following N lines form an N × N matrix P. The matrix elements pij (0 ≤ pij ≤ 2000) determines the cost of minibus from the ith shop to the jth shop. If pij = 0, it means that there is no direct minibus route connecting the shops number i and j. The matrix is symmetric, and all pii are zero.
The next line holds a single integer number K (1 ≤ K ≤ 50), the number of types of groceries.
The next line holds K integers Qi (1 ≤ Qi ≤ 2000), the required amount of each grocery type on Grisha's shopping list.
What follows is K blocks describing the grocery stocks and prices in the shops. The ith block starts with a line holding a single integer M, the number of shops that have the ith grocery type. Each of the M following lines of the block holds three integers v, p, q (1 ≤ v ≤ n, 0 ≤ p ≤ 2000, 1 ≤ q ≤ 2000) meaning that the shop number v sells the ith grocery type for p rubles per piece and it has q pieces of that grocery.
A single number, the minimum sum of money that will allow Grisha to buy all the groceries. If that is impossible, output - 1.
Solutions that fail the test in the example will be awarded 0 points and not be further tested.
Each test is scored separately.
5
0 1 3 0 2
1 0 5 0 5
3 5 0 7 2
0 0 7 0 2
2 5 2 2 0
3
3 5 5
3
1 3 2
3 2 1
5 4 3
3
2 4 3
3 5 4
5 2 1
4
1 9 1
2 8 2
3 7 3
4 6 1
70