Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

A. Environment-Friendly Travel
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Taking holidays, unfortunately, has a carbon footprint. The $$$\mathtt{CO}_2$$$-cost of a kilometer traveled depends on the mode of transportation. For instance, train travel is less costly than bus travel, which is itself less costly than car travel.

Your objective is to plan a holiday trip from your house, given by 2D coordinates $$$(x_s , y_s)$$$ , to your travel destination, given by $$$(x_d , y_d)$$$. Being aware of the environmental impact of travel, you want to minimize the $$$\mathtt{CO}_2$$$-cost of your holiday, but you still want to keep the total number of kilometers traveled within a given budget $$$B$$$.

To aid you in planning, you have access to a map of $$$N$$$ stations, possibly linked by $$$T$$$ different modes of transportation (airplane, train, etc.) numbered $$$1,\ldots, T$$$. Each mode has a $$$\mathtt{CO}_2$$$-cost per distance unit $$$C_1 , \ldots , C_T$$$. You can travel by car from your home to the destination, from your home to any station, and from any station to the destination point, at a cost $$$C_0$$$ per distance unit. $$$C_0$$$ is always greater than any of $$$C_1, \ldots, C_T$$$. Each of the $$$N$$$ stations has coordinates $$$(x_i , y_i)$$$ for $$$i = 0,\ldots, N - 1$$$. Each station may be connected to some other stations via one or several of the $$$T$$$ modes. Each connection works both ways, so only one direction has to be listed. There can be multiple modes of transportation available between two stations. You can only travel between two stations via their connections using the available transportation modes (car travel is not allowed between stations).

The distance between two points $$$a$$$ and $$$b$$$ is the 2D distance between $$$(x_a , y_a)$$$ and $$$(x_b , y_b)$$$, rounded to the nearest integer above: $$$$$$ \mathop{dist}(a, b) = \left\lceil\sqrt{(x-a)^2+(x-b)^2}\right\rceil, $$$$$$ and the $$$\mathtt{CO}_2$$$-cost of travel between $$$a$$$ and $$$b$$$, using transport mode $$$i$$$ is: $$$$$$ \mathop{cost}(a, b, i) = C_i \times \mathop{dist}( a, b ). $$$$$$ Given two source–destination coordinates, a budget $$$B$$$ expressed in distance units, a list of transportation modes and their respective $$$\mathtt{CO}_2$$$ -costs, and the station network, your task is to compute the minimal $$$\mathtt{CO}_2$$$ -cost possible while traveling at most $$$B$$$ kilometers.

Input

The input consists of the following lines:

  • Line 1 contains two space-separated integers, $$$x_s$$$ and $$$y_s$$$, the coordinates of your house.
  • Line 2 contains two space-separated integers, $$$x_d$$$ and $$$y_d$$$, the coordinates of your destination.
  • Line 3 contains an integer, $$$B$$$, the maximal distance (in kilometers) that you accept to travel.
  • Line 4 contains an integer, $$$C_0$$$, the $$$\mathtt{CO}_2$$$-cost per distance unit of traveling by car.
  • Line 5 contains an integer, $$$T$$$, the number of modes of transportation (beside cars).
  • Line $$$i + 5$$$, for $$$1 \le i \le T$$$, contains the integer $$$C_i$$$ , the $$$\mathtt{CO}_2$$$-cost per distance unit of transportation mode $$$i$$$.
  • Line $$$T + 6$$$ contains the integer $$$N$$$, the number of stations.
  • Line $$$i + T + 7$$$ describes station $$$i$$$ ($$$0 \le i \lt N$$$) and contains $$$3 + 2 \times l_i$$$ space-separated integers. The first three integers are $$$x_i$$$ , $$$y_i$$$ and $$$l_i$$$. The pair ($$$x_i, y_i$$$) represents the coordinates of station while $$$l_i$$$ is the number of links between station $$$i$$$ and other stations. The $$$l_i$$$ remaining pairs of integers ($$$j, m_j$$$) each describe a link to station $$$j$$$ ($$$0 \le j \lt N$$$) using transportation mode $$$m_j$$$ ($$$1 \le m_j \le T$$$). All links are bidirectional.

Limits: All inputs are integers. All coordinates are in $$$[0, 100] \times [0, 100 ]$$$.

  • $$$1 \le T \le 100$$$;
  • $$$1 \le N \le 1000$$$;
  • $$$0 \le B \le 100$$$;
  • $$$1 \le C_1 , \ldots , C_T \lt C_0 \le 100$$$;
  • for each station, there are at most 100 links to other stations.
Output

The output should contain a single line with a single integer representing the minimal feasible $$$\mathtt{CO}_2$$$-cost or $$$-1$$$ if no feasible cost is found within the kilometer budget.

Example
Input
1 1
10 2
12
100
2
10
50
3
2 3 2 1 1 2 2
5 5 1 2 1
9 3 0
Output
850
Note

Sample Explanation

The results corresponds to the $$$\mathtt{CO}_2$$$-cost of the following route:

  1. from home at (1,1) to station 0 at (2,3) by car for a cost of $$$100 \times\lceil\sqrt{1^2+ 2^2}\rceil = 300$$$,
  2. to station 2 at (9,3) via transportation mode 2 for a cost of $$$50\times\lceil\sqrt{7^2 +0^2}\rceil = 350$$$,
  3. to the destination at (10,2) by car for a cost of $$$100 \times \lceil\sqrt{1^2+1^2}\rceil = 200$$$ for a total of 850.
This route is valid because the total distance traveled is $$$3 + 7 + 2 = 12$$$, within the allowed budget of 12.