U508299 Traveling

[You can visit **THE ENGLISH FORMAT** to look at this problem easily.](https://www.luogu.com.cn/problem/U508303)

小 T 和 小 L 计划出去旅游（~~赚钱~~）。 小 T 在看地图。 地图上标注了 $N$ 个城镇，编号从 $1$ 到 $N$。 $M$ 条铁路把这些城镇联系了起来：第 $i$ 条道路连通了城镇 $U_i$ 和 $V_i$。 他们可以选择从任意一个城镇 $S$ 做起点开始旅游，然后沿着铁路到处玩耍。游玩某个城镇 $T$ 后，他们也可以结束旅程回家。 作为学生， 小 T 和 小 L 当然没有足够的钱环游世界，他们计划在旅游的同时打工赚钱。具体而言，经过详尽的调研，他们已经知道在第 $i$ 个城市可以得到 $D_i$ 的打工收入。 小 T 和 小 L 的计划是，在整个旅游的过程，累计的收入尽量大。 但是，由于旅游的起点城镇 S 是坐飞机抵达的，所以飞机抵达第 i 个城镇需要付出是 $J_i$ 的机票钱。 “合理安排路线，选择恰当的起点 $S$ 和终点 $T$ 的话，我们这次旅游，能赚多少钱？” 小 T 已经开始在计算了。

输入数据共有 $M+3$ 行。 第一行是两个数 $N$ 和 $M$。 接下来 $M$ 行，每行有两个数 $U_i$ 和 $V_i$。 接下来一行，有 $N$ 个数，第 $i$ 个数是在城镇 $i$ 的打工收入 $D_i$。 接下来一行，有 $N$ 个数，第 $i$ 个数是选择 $i$ 作为游玩起点 $S$ 需要付出的机票价格 $J_i$。

输出数据共有 $1$ 行。 输出一个数 $ans$，表示游玩结束后可能获得的最多收入（打工所得 $-$ 机票钱）。 特别的，如果无论如何设计路线，打工所得连机票钱都攒不够的话，**则 $ans \gets$ 他们最少可能要亏的钱（自然数）**。

对于 $20\%$ 的数据，$N \le 16$； 对于 $50\%$ 的数据，$N \le 1000$； 对于 $100\%$ 的数据，$N \le 100000$，$1 \le D_i,L_i,J_i \le 10^9$，$1 \le U_i,V_i \le N$，$1 \le M \le 100000$，保证没有重边和自环。