406710: GYM102503 G Sharing Chocolates 8: The Last Jebediah

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.

The 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.

For each test case, output a single line containing a single integer denoting the maximum total science your ship can collect.

$$$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.

1
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 200

16000