019 - stamp rally

問題

HOJ街ではスタンプラリーを開催しています。
この街にはいくつかの駅があり、駅$i$にはスタンプ$C_i$が置かれています。
また、いくつかの電車が走っていて、$j$番目の電車では駅$U_j$から駅$V_j$まで一方通行の移動ができます($U_j < V_j$)。

スタンプラリーには以下のルールがあります。
・スタンプ帳には最大$K$個のスタンプしか押すことができない。
・各駅ではスタンプ帳にスタンプを押すかどうか選択ができる。
・スタンプラリーはどこの駅から開始してもいい。

このスタンプラリーでスタンプの総和の最大値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$
$C_1$ $C_2$ ... $C_N$
$U_1$ $V_1$
$U_2$ $V_2$
 :
$U_M$ $V_M$

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq N,M \leq 10^{4}$
• $1 \leq K \leq 10^{3}$
• $1 \leq C_i \leq 10^{6}$
• 入力はすべて整数

部分点

部分点1は以下の制約を満たす。(点数の20%)

$M = N-1$

$U_i = i,V_i = i+1(1 \leq i \leq N-1)$

入出力例

入力例1

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

出力例1

9

駅4,駅5のスタンプを押すのが適切です。

入力例2

4 2 3
1 7 3 2
1 2
3 4

出力例2

8

駅1,駅2のスタンプを押すのが適切です。