408216: GYM103055 J Grammy and Jewelry

There is a connected undirected graph with $$$n$$$ vertices and $$$m$$$ edges. Vertices are indexed from $$$1$$$ to $$$n$$$. There is infinite jewelry in vertex $$$i$$$ ($$$2\leq i\leq n$$$), each valued $$$a_i$$$. Grammy starts at point $$$1$$$. Going through each edge consumes $$$1$$$ unit of time. She can pick up a piece of jewelry at vertex $$$i$$$ and put it down at vertex $$$1$$$. Picking up and putting down a piece of jewelry can be done instantly. Additionally, she can carry at most 1 piece of jewelry at any time. When she put down a piece of jewelry valued $$$x$$$ at vertex $$$1$$$, she obtains the value of it. Now, for each $$$k$$$ between $$$1$$$ and $$$T$$$ (inclusive) she wonders what is the maximum value she can get in $$$k$$$ units of time.

The input contains only a single case.

The first line contains three integers $$$n$$$, $$$m$$$, and $$$T$$$ ($$$1\leq n,m,T\leq 3\,000$$$).

The second line contains $$$n-1$$$ integers $$$a_2, a_3, \dots, a_n$$$ ($$$1\leq a_i\leq 3\,000$$$).

The following $$$m$$$ lines describe $$$m$$$ edges. Each line contains 2 integers $$$x_i$$$ and $$$y_i$$$ ($$$1\leq x_i,y_i\leq n$$$), representing a bidirectional edge between vertex $$$x_i$$$ and vertex $$$y_i$$$.

Note that the graph may contain self-loops or duplicated edges.

Print $$$T$$$ integers in one line, the $$$k$$$-th ($$$1\leq k\leq T$$$) of which denoting the maximum value she can get in $$$k$$$ units of time.

5 6 5
2 3 4 5
1 2
4 5
1 4
2 3
1 3
3 3

0 4 4 8 8