【East!_XVI】九尾妖狐

2015年4月4日1,6390

Background

某无良设计师伊泽瑞尔:刀妹太弱了,我们来增强阿狸吧。

Description

阿狸现在有 N 个技能,伊泽瑞尔要决定它们是 AD 技能还 是AP技能。

因为出装不同,所以当一个技能是 AP 时,阿狸的爆发增加 ap_i,当一个技能是 AD 时,阿狸的爆发增加 ad_i。

有些技能配合可以打出伤害加成,这样阿狸的技能就可以被 表示为一张无向图。当有关联的两个技能都是 AD 时,阿狸的爆 发增加 AD_i,当两个技能都是 AP 时,阿狸的爆发增加 AP_i, 当两个技能不同类时阿狸的爆发减少 Ahr_i。

求阿狸最多增加多少爆发。

Input

第一行两个整数 N,M 表示阿狸有 N 个技能,无向图有 M 条边。

接下来 N 行每行两个整数 ap_i,ad_i。
接下来 M 行每行五个整数 u,v,AD_i,AP_i,Ahr_i。

Output

输出一行一个整数,表示阿狸的爆发最多增加多少。

Sample Input

10
1234 4321

Sample Output

4321

Data Constraint

序号

N

M

1

5

5

2

50

100

3

100000

0

4

500000

0

5

1000

3000

6

1000

3000

7

1000

3000

8

10000

40000

9

10000

40000

10

10000

40000

所有数据不爆long long且均为整数

After Problem

鉴于伊泽瑞尔的风筝能力太强,所以基兰把伊泽瑞尔的技能 移除了,但是他的普通攻击被增加了粒子特效,现在伊泽瑞尔看 起来更酷炫了。

题解

最小割 同文理分科