U495341 抱佛脚

马上就要考CSP-S了，OID还是啥都没复习。因为教练的刀架在了脖子上，所以……**她决定去佛山抱佛脚qaq**

佛山有 $n$ 尊佛，佛分为大佛和小佛，有 $d$ 尊大佛。每尊佛拜（抱）一次能获得 $a_i$ 的保佑，拜（抱）两次可以累加。 佛山有个规矩，每尊大佛最多拜（抱）两次，小佛最多拜（抱）一次，多了会~~天降神罚~~，经过一尊佛必须拜（报）。 每尊佛都在不同的地方，有 $m$ 条道路双向连接第 $u_i$ 和 $v_i$ 两尊佛。道路有长短，那么OID走过第 $i$ 条道路需要花费 $w_i$ 的力气。不过，为了人们能拜（抱）更多的佛，所有的大佛脚下会有休息站，第 $i$ 尊大佛会使OID恢复 $r_i$ 的力气。如果所有佛都拜（抱）完了，或者OID的力气不足以让她去往下一尊佛，那么抱佛脚结束。 现在给定OID的初始力气 $s$，假定她一开始在第 $1$ 尊佛的位置，那么她最多能获得多少佛祖保佑？

第一行三个正整数 $n,m,s$，分别表示佛的数量，道路数量和OID的初始力气。 第二行 $n$ 个正整数 $a_i$，表示第$i$尊佛拜（抱）一次能得到的保佑。 第三行 $n$ 个正整数 $b_i$，如果 $b_i=0$ 表示这是一尊小佛，$b_i=1$ 表示这是一尊大佛。 接下来 $m$ 行，每行三个正整数 $u_i,v_i,w_i$，表示从第 $u_i$ 尊佛到第 $v_i$ 尊佛有一条OID需要花费 $w_i$ 力气的道路。 最后一行 $d$ 个正整数 $r_i$，表示第 $i$ 尊大佛使OID恢复的力气。

一行一个正整数，表示OID最多能获得的佛祖保佑。

**【数据范围】** - $1 \le n,m \le 10^5$，$1 \le s,w_i,r_i \le 10^9$ - $1 \le a_i \le 10^4$，$1 \le u_i,v_i \le n$ 数据保证没有重边和自环。 **【提示】** 样例解释：经过佛的顺序为 $1→2→4→1→3$，剩余力气为 $1$，不足以去往第 $5$ 尊佛，所以最终保佑为 $5+2+3+5+1=16$。 休息站休息次数和拜（抱）次数的规定没有任何关系；对于大佛，可以连续拜（抱）两次，也可以经过两次分开拜（抱）。