auto

I live in Iasi (let's just write it down as A to keep it simple) and I have to get to Bucharest (let's write it down as B) within T hours.
I only drive on the freeway, at maximum legal speed, so I got a map that marks the N cities in the country as well as the M freeways that connect the cities. Each freeway connects two cities.
The map is very detailed and also shows freeway taxes and parking costs for every city.
I don't have to pay for parking in my city (A) and in the destination city (B) but if I want to stop in any other city I have to pay a parking tax (e.g.: to park in city i, the parking tax will be RON p_i /hour).
Freeway taxes vary depending on when I get on the freeway. The tax is paid per hour of driving on the freeway so if I traveled on a freeway h hours and when I got on the freeway the tax was c, when I get off the freeway I am going to pay RON c*h.

Task

Write a program that determines the minimum total amount (cost of parking + freeway taxes) that I have to pay to get from city A to city B in maximum T hours.

Input Data

Input file auto.in contains on the first line two positive integers separated by a space, N M, representing the number of cities and, respectively, the number of freeways.
The second line contains 3 positive integers separated by a space, A B T, representing the departure city, destination city and the maximum time in which I have to get to my destination.
The third line contains N positive integers each separated by a space, p₁ p₂ ... p_n, representing the parking cost/hour for each of the N cities.
The next 2*M lines contain information about the M freeways, 2 lines for each freeway. The first of the two lines contains 3 positive integers each separated by a space, O1 O2 D, meaning "the freeway connects cities O1 and O2, and crossing it takes D hours at the maximum speed limit". The second line contains T positive integers each separated by a space, c₀ c₁ ... c_T-1, where c_i represents the cost for one hour of driving on said freeway, if we came in on it at time i.

Output Data

Output file auto.out will contain a single line with one positive integer, representing the total minimum amount I am going to pay in order to get from city A to city B.

Constraints

• 0 < N, T <= 100
• M <= 500
• 0 <= p_i, c_i <= 100
• I leave city A at time 0.
• There is at most one freeway between two cities.
  

Time limit: 0.3 seconds/test

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com