1896 - stamp rally

時間制限 1 秒 / メモリ制限 64 MB / 得点 10 / Writer ei2332 / x 1 / 統計 /

TLE
1sec
MLE
64MB
得点
10

問題

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のスタンプを押すのが適切です。