In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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
into a metal
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.
Help to cure Byteotian economy! Write a program which:
In the first line of the standard input there is one positive integer n denoting
the number of different metals, . In the
-st line, for
, there is a
non-negative even integer
: the price of 1 kg of the
-th metal,
. We assume that gold has
the number 1. In the
-nd line there is one non-negative integer
equal to the number of transformation processes the alchemists are
able to conduct,
. In each of the following
lines there are three positive integers, separated by single
spaces, describing consecutive transformation processes. A triple of numbers
,
,
denotes that the alchemists are able
to obtain the
-th metal from the
-th metal, and they
demand
bytealers for transforming 1 kg of material,
,
. An ordered pair of numbers
and
may appear at most once in the data.
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.
For the 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 result is:
60
Task author: Lukasz Kowalik.