Polish version    English version  
  History of OI -> X OI 2002/2003 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Rules
For contestants
Helpful resources
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
X Olympiad in Informatics 2002/2003
Problem: Smugglers
Author: Lukasz Kowalik

Byteotia is famous for its rich deposits of gold. Therefore, for many years there flourished the sale of that metal to a neighbouring kingdom, Bitland. Unfortunately, the growing deficit of the national budget forced the king of Bitland to introduce heavy tariffs on metals and minerals. Traders crossing the border have to pay customs duty of 50% of the value of the transported load. Byteotian merchants are threatened with bankruptcy. Fortunately, Byteotian alchemists have developed ways to transform some metals into other. The merchants' idea is to use the alchemists' know-how to transform gold into some cheap metal, and next, after crossing the border and paying little tariff, to transform it back into gold. Unfortunately, the alchemists can not transform any metal into arbitrarily chosen other one. Therefore, it may happen that the process of obtaining a given metal from gold must be a chain of transformations that produces a different metal on each stage. The alchemists demand stiff fees for their services. They have fixed a price for transforming 1 kg of a metal A into a metal B for each transformation they are able to conduct. The traders ponder on what form gold should be transported across the border and what sequence of alchemical processes should be applied to achieve the highest income.

Task

Help to cure Byteotian economy! Write a program which:
  • Reads a table of prices for all metals and prices for transformations offered by the alchemists.
  • Determines such a sequence of metals m1, m1, ..., mk that:
    • m1 = mk is gold,
    • for each i=2, 3, ..., k the alchemists are able to obtain metal mi from metal mi-1, and
    • the cost of performing the whole sequence of alchemical processes for 1 kg of gold, augmented by the duty paid on the border (50% of the price of 1 kg of the cheapest metal from mi, for i = 1, 2, ..., k) is the smallest possible.
    We assume that during the alchemical processes the weight of metals does not alter.
  • Writes out the cost of performing the determined sequence of alchemical processes augmented by the duty paid on the border.

Input

In the first line of the standard input there is one positive integer n denoting the number of different metals, 1 <= n <= 5000. In the (k+1)-st line, for 1 <= k <= n, there is a non-negative even integer pk: the price of 1 kg of the k-th metal, 0 <= pk <= 109. We assume that gold has the number 1. In the (n+2)-nd line there is one non-negative integer m equal to the number of transformation processes the alchemists are able to conduct, 0 <= m <= 100000. In each of the following m lines there are three positive integers, separated by single spaces, describing consecutive transformation processes. A triple of numbers a, b, c denotes that the alchemists are able to obtain the b-th metal from the a-th metal, and they demand c bytealers for transforming 1 kg of material, 1 <= a,b <= n, 0 <= c <= 10000. An ordered pair of numbers a and b may appear at most once in the data.

Output

Your program should write to the standard output. In the first line there should be one integer - the cost of performing the alchemical processes determined by your program augmented by the duty paid on the border.

Example

For the following input data: 
4
200
100
40
2
6
1 2 10
1 3 5
2 1 25
3 2 10
3 4 5
4 1 50
the correct answer is in the following output: 
60



Print friendly version