这题假了

【题目背景】

[——《花海》]

不要你离开  

回忆划不开

【题目描述】

zfy开始了回忆。

zfy的回忆中有 $n$ 个情节，编号从 $1$ 到 $n$，第 $i$ 个情节有一个“美好值”$a_i$。这些情节间有 $m$ 个形如 $u,v,x,y$ 的联系，表示zfy可以从第 $u$ 个情节开始回忆，回忆起第 $v$ 个情节。同时，在这次回忆后，第 $x$ 个和第 $y$ 个情节也建立了联系，表示 zfy 可以从第 $x$ 个情节开始回忆，回忆起第 $y$ 个情节。

zfy这次回忆的$初始“美好值”$为 $s$，当回忆起情节 $i$ 时zfy这次回忆的“美好值”就会增加 $a_i$，重复回忆一个情节不会使“美好值”发生二次变化。

zfy会从第一个情节开始回忆，他想回忆起第 $n$ 个情节，但zfy不想使这次回忆的“美好值”在任何一个时刻为负，求回忆起第 $n$ 个情节时zfy这次回忆的最大“美好值”，若无法回忆起第 $n$ 个情节，输出 $-1$。

请注意本题特殊的时空限制。

【输入格式】

第一行四个整数 $c,n,m,s$，表示子任务编号（样例为 $-1$），情节数，联系数，初始“美好值”。

接下来一行有 $n$ 个空格隔开的整数 $a_i$，表示这 $n$ 个情节的“美好值”。

接下来 $m$ 行，每行有四个正整数，分别为上面提到的 $u,v,x,y$。特别的，当 $x,y$ 都等于 $0$ 时代表这次回忆不会建立新的联系。

【输出格式】

输出 $1$ 个整数，即你的答案，或报告无解。

【样例输入】

-1 4 4 5
3 2 -1 5
1 2 0 0
2 3 3 2
3 2 0 0
3 4 0 0

【样例输出】

14

【数据规模与约定】

对于 $100\%$ 的数据，$1\le c\le 4$, $1\le n\le 10^3$，$1\le m\le 10^4$，$1\le s\le 10^5$，$-10^5\le a_i\le 10^5$，$1\le u, v\le n$，$0\le x,y\le n$，没有子任务依赖，保证数据随机。

保证时间在std的1.5倍以上，空间在std的3倍以上。

【后记】

[——《花海》]

天空仍灿烂  

她爱着大海

【来源】

luogu U663632

感谢谷友 _DEQUE_，myl_coder，wayneoi，William_zx，zifeiwoye，zhouzihan20110620 帮忙验题