白子的情人节礼物

题面背景

我永远喜欢砂狼白子！ ----MyShiroko

白子最近有点烦恼，因为她敏锐的嗅觉闻到了星野前辈身上有老师的味道。（详见《一日一星野》）

在多次询问星野无果的情况下，她打算直接去夏莱找老师问个清楚。

不过最近情人节快到了，白子决定拿着一些礼物，所以她骑行去了海边，钓鱼！

在海边上有 \(n\) 个区域，每个区域有 \(a_i\) 条鱼，白子最多能在每个区域钓起 \(b_i\) 条鱼。

而且为了防止每个区域内的鱼被钓光，在某两个区域内的鱼之间有一条通道，每个区域的鱼可以往别的区域游，但是只能游 \(c_i\) 只鱼。

请帮白子想想，她最多能钓到几条鱼？

输入格式

第一行给出三个整数 \(n\)、\(m\)。分别代表鱼池的个数、通道的个数

第二行给出 \(n\) 个整数，第 \(i\) 个数代表 \(a_i\) 。

第三行给出 \(n\) 个整数，第 \(i\) 个数代表 \(a_i\) 。

接下来 \(m\) 行，每行三个整数 \(u\)、\(v\)、\(w\)。代表第 \(u\) 个区域和第 \(v\) 个区域有一条能容纳 \(w\) 条鱼经过的通道。

输出格式

一行一个整数。输出白子最多能钓上来的鱼数。

QwQ,白子这么可爱，你一定会来帮助白子的对吧。

样例输入1：

3 2 
10 7 3
3 9 4
1 2 1
1 3 2

样例输出1：

15

样例输入2：

10 10
3 20 8 23 35 9 27 42 33 17 
24 26 45 31 45 23 40 45 19 26 
9 5 5
8 5 23
6 9 17
8 7 20
10 6 44
6 7 20
8 9 39
3 4 35
3 10 7
2 7 26

样例输出2：

217

样例输入3：

10 10
2045015393 734786021 630365562 1624037611 1097890704 1811927582 1548753970 1581479305 2030682064 126741973 
1649947418 209040697 719358622 1367809914 645805854 2029513737 1712230785 854662374 1786247468 737653066 
2 4 1661877023
7 2 915948448
5 10 729981197
8 5 1464767218
1 9 415174275
5 9 1996653580
2 1 539028428
6 7 1184834282
6 4 2039496657
6 10 641660070

样例输出3：

11623276875

QwQ,白子这么可爱，你一定回来帮助白子的对吧。

数据范围:

对于 30% 的数据 \(n \leq 500\) 、\(m \leq 3000\)。

对于 50% 的数据 \(n,m \leq 10000\)。

对于全部的数据 \(n,m \leq 100000\)。

tip: 时限是标算的两倍以上

题解