我早就被幸福所包围了

题目背景

こんなにも、たくさんの幸せをあの人に分けてもらった だから、きっと 今の、私は 誰が何と言おうと

世界一、 幸せな女の子だ

————クト・リノタ・セニオリス

题目描述

“假如……我是说假如喔。万一我再过五天就会死，你能不能对我温柔一点？”

珂朵莉又去出征了，但威廉并不知道她要打开妖精乡之门。威廉答应了珂朵莉为她做蛋糕，所以他要辗转于各个天空岛上做一次交易。一共有 $n$ 座天空岛，各岛之间有 $m$ 条航线，每座岛的交易价是$v_i$，每条航线的票价是 $w_i$，且可单项可双向，经过 $i$ 号岛消耗 $v_i$ 元，在点上可进行贸易，花费 $v_i$ 买入或卖出物品以消耗或得到货币，最多贸易一次，有 $k$ 次机会乘坐灰岩皮将军的飞艇，可以免于某条航线的票价 $w_i$。

输入格式

输入共有 $n+m+1$ 行。

第一行三个整数，分别为 $n、m、k$

接下来一行 $n$ 个整数，代表 $v_i$ 。

接下来 $m$ 行，每一行分别为一条边的起点、终点和、$w_i$ 和 $opt$ 。若 $opt$ 为 $1$ ，则为单向边，若 $opt$ 为 $2$ ，则为双向边。

输出格式

输出共有 $1$ 行，表示最大货币得数。

样例 #1

样例输入 #1

5 6 1
1 100 100 100 1000
1 2 10 1
1 4 100 2
2 4 10 1
2 3 10 1
3 5 10 1
4 5 2 1

样例输出 #1

9997

提示

对于$100$%的数据，保证 $1 \leqslant n\leqslant 2*10^3$，$n-1 \leqslant m\leqslant 10^4$，$1 \leqslant k\leqslant 3$ , $1 \leqslant v_i\leqslant 10^9$，$1 \leqslant w_i\leqslant 10^3$ 。