最后一次点单 - 問題

你正在尝试一次横跨全镇的传奇串酒吧（pub crawl）之旅。

小镇有 $k$ 个交叉路口，由 $m$ 条道路连接。每个交叉路口都有一家酒吧。每条道路都可以双向通行，且具有非负的行驶时间。同一对交叉路口之间可能存在多条道路。你在时间 $0$ 时从 $1$ 号酒吧开始你的串酒吧之旅。

酒吧 $i$ 位于交叉路口 $i$，并将在绝对时间 $c_i$ 关闭。一杯酒必须在关门时间或之前喝完才算数。

随着夜幕降临，你的饮酒能力会发生变化：喝第 $1$ 杯酒需要 $t_1$ 个时间单位，喝第 $2$ 杯需要 $t_2$ 个时间单位，依此类推，喝第 $r$ 杯需要 $t_r$ 个时间单位。请注意，$t_i$ 不一定是递增的。

你可以按任意顺序访问酒吧（不一定非要从在 $1$ 号酒吧喝酒开始），并且可以多次返回同一家酒吧，但你不能在同一家酒吧连续喝两杯酒。

你的任务是在所有酒吧关门之前，最大化喝掉的酒的杯数。

第一行包含一个整数 $r$（$1 \le r \le 100$），表示你最多能喝的酒的杯数。
第二行包含 $r$ 个整数 $t_1 \dots t_r$（$1 \le t_i \le 3600$），表示喝每杯酒所需的时间（秒）。
第三行包含一个整数 $k$（$1 \le k \le 300$），表示酒吧的数量。
第四行包含 $k$ 个整数 $c_1 \dots c_k$（$1 \le c_i \le 86400$），表示各酒吧的关门时间（秒）。
第五行包含一个整数 $m$（$1 \le m \le 90000$），表示道路的数量。
接下来的 $m$ 行，每行包含三个整数 $a$、$b$ 和 $d$，表示酒吧 $a$ 和 $b$ 之间有一条双向道路，行驶需要 $d$ 秒（$1 \le a, b \le k$ 且 $a \ne b$；$1 \le d \le 86400$）。请注意，同一对酒吧之间可能有多条道路。

输出一个整数，表示在所有酒吧关门之前你最多可以喝掉的酒的杯数。

8
60 120 180 240 300 360 420 480
2
900 1500
1
2 1 90

10
2 2 2 2 2 3 3 3 3 3
4
35 30 15 30
4
1 2 5
3 4 1
4 1 5
3 2 1

QOJ.ac