该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

你生于战国初期，是一个粮商。当时有 $N$ 个国家陷于战乱，各国粮价起伏不定，商道纵横交错。

乱世之中，粮价如潮，路费如刀。 能算清一箱粮的盈亏，方为真商贾； 能算清千条路的最优，方为鬼才。

题目描述

规则

• 买粮：在国家 $i$，每箱花费 $W1_i$ 金
• 卖粮：在国家 $i$，每箱获得 $W2_i$ 金
• 运粮道：$M$ 条单向道路，从国家 $u$ 到国家 $v$，过路费为 $w$ 金

约束

• 初始你有 $P$ 金，从国家 1 出发
• 图是 DAG（有向无环图）
• 每个国家只能访问一次（路径为简单路径）
• 到达一个国家时，必须进行一次行动：买粮 或 卖粮（二选一）
• 运粮道单向通行，需支付路费，路费从当前金钱中扣除

目标

求你能获得的最高金。

输入格式

N P
W1_1 W1_2 ... W1_N
W2_1 W2_2 ... W2_N
M
u_1 v_1 w_1
u_2 v_2 w_2
...
u_M v_M w_M

输出格式

一个整数，表示最高金。

样例

输入

4 10
1 10 10 10
1 1 10 0
3
1 4 0
1 2 0
1 3 0

输出

100

解释：

• 国家 1：$W1_1 = 1$，用 10 金买 10 箱粮，剩 0 金
• 走 $1 \to 3$，路费 0，到国家 3
• 国家 3：$W2_3 = 10$，卖 10 箱得 100 金
• 路径结束，最高金 100

数据范围