406710: GYM102503 G Sharing Chocolates 8: The Last Jebediah
Description
Congratulations!
Today is your day
You're off to a galaxy far, far away
You have fuel in your tank
You have goo with your crew
Now it's time to prepare for your mission anew
There are planets and giants and comets to see
But alas you are limited in Delta V
It is this that you use to move between stars
And planets and orbits and even to Mars
There are $$$n$$$ little planets to visit and see
And $$$m$$$ routes between them you can follow with glee
For a route between two planets we call $$$a$$$ and $$$b$$$
There is cost $$$c_{a,b}$$$ given in Delta V
Your ship has a tank with a limit called $$$V$$$
How sad in this world that nothing is free
And one more thing that makes it much harder to do
Is the route between things are just one way for you
The rocket ship works for just one way you see
Just blame the developers of KSP
If you go to a planet there is no way back
Not a hole or a mole or even a crack
There's no cycles or circuits or loops to be had
In this galaxy that is a little bit sad
Each planet you visit will have science $$$s_i$$$
The total you get, you must make it high
As high as you can, as high as the sky
As high as it goes, as high as a TIE
On Kerbin you start which is planet zero
And onward you go our almighty hero
Think back on your friends, on Alvin and Berto
And chocolates shared and other dessert-o
"This is your last chance," I say with a sigh
Oh poor Jebediah your fate is to die
—
As the captain, pilot, and only crew member of the next mission of the Kerbal Space Program, you must maximize the total science collected by your ship. As your ship passes by a planet $$$i$$$, your ship collects $$$s_i$$$ science points.
Your ship has a fuel capacity $$$V$$$ given in Delta V. It costs $$$c_{a,b}$$$ Delta V to move from planet $$$a$$$ to planet $$$b$$$. In addition, the Kerbal solar system has a peculiar property where it is guaranteed that there is no way to return to any planet $$$a$$$ once you've left that planet.
You start on planet zero, also known as Kerbin.
InputThe first line of input contains $$$t$$$, the number of test cases.
The first line of input contains three space-separated integers $$$n$$$, $$$m$$$ and $$$V$$$. The planets are numbered $$$0$$$ to $$$n-1$$$.
The second line contains $$$n$$$ space-separated integers $$$s_0, s_1, \ldots, s_{n-1}$$$.
The next $$$m$$$ lines describe the routes. Each line contains three space-separated integers $$$a$$$, $$$b$$$ and $$$c_{a,b}$$$ indicating that there is a route that lets you move from planet $$$a$$$ to planet $$$b$$$ with a cost of $$$c_{a,b}$$$ Delta V.
OutputFor each test case, output a single line containing a single integer denoting the maximum total science your ship can collect.
Scoring$$$1 \le t \le 1000$$$
$$$1 \le n \le 6000$$$
$$$0 \le m \le 12000$$$
$$$0 \le V \le 6000$$$
The sum of the $$$n$$$s in a single file is $$$\le 6000$$$.
The sum of the $$$m$$$s in a single file is $$$\le 12000$$$.
$$$0 \le a, b < n$$$
$$$a \not= b$$$
For every pair of planets $$$(a, b)$$$, there is at most one route from $$$a$$$ to $$$b$$$.
For every planet, there is a sequence of routes from planet $$$0$$$ to that planet.
There is no way to return to any planet $$$a$$$ once you've left that planet.
$$$0 \le c_{a,b} \le 10^9$$$
$$$0 \le s_i \le 10^9$$$
Subtask 1 (20 points):
$$$n \le 8$$$
The sum of the $$$n$$$s in a single file is $$$\le 600$$$.
Subtask 2 (20 points):
$$$n \le 20$$$
The sum of the $$$n$$$s in a single file is $$$\le 600$$$.
Subtask 3 (30 points):
$$$n \le 120$$$
The sum of the $$$n$$$s in a single file is $$$\le 600$$$.
Subtask 4 (15 points):
$$$c_{a,b} = 1$$$
$$$s_i = 1$$$
Subtask 5 (15 points):
No additional constraints.
ExampleInput1 6 8 1200 4200 9000 5000 2000 4800 5000 0 1 350 0 2 300 1 3 400 2 3 300 2 5 9001 3 4 500 3 5 650 4 5 200Output
16000