#NOI2020A. 美食家

美食家

题目描述

坐落在 Bzeroth 大陆上的精灵王国击退地灾军团的入侵后,经过十余年的休养生息,重新成为了一片欣欣向荣的乐土,吸引着八方游客。小 W 是一位游历过世界各地的著名美食家,现在也慕名来到了精灵王国。

精灵王国共有 nn 座城市,城市从 11nn 编号,其中城市 ii 的美食能为小 W 提供 cic_i 的愉悦值。精灵王国的城市通过 mm单向道路连接,道路从 11mm 编号,其中道路 ii 的起点为城市 uiu_i,终点为城市 viv_i,沿它通行需要花费 wiw_i 天。也就是说,若小 W 在第 dd 天从城市 uiu_i 沿道路 ii 通行,那么他会在第 d+wid + w_i 天到达城市 viv_i

小 W 计划在精灵王国进行一场为期 TT 天的旅行,更具体地:他会在第 00 天从城市 11 出发,经过 TT 天的旅行,最终在恰好第 TT回到城市 11 结束旅行。由于小 W 是一位美食家,每当他到达一座城市时(包括第 00 天和第 TT 天的城市 11),他都会品尝该城市的美食并获得其所提供的愉悦值,若小 W 多次到达同一座城市,他将获得多次愉悦值。注意旅行途中小 W 不能在任何城市停留,即当他到达一座城市且还未结束旅行时,他当天必须立即从该城市出发前往其他城市。

对于上图,小 W 一种为期 1111 天的可行旅游方案为 1212311\rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1

  • 00 天,小 W 从城市 11 开始旅行,获得愉悦值 11 并向城市 22 出发。
  • 11 天,小 W 到达城市 22,获得愉悦值 33 并向城市 11 出发。
  • 44 天,小 W 到达城市 11,获得愉悦值 11 并向城市 22 出发。
  • 55 天,小 W 到达城市 22,获得愉悦值 33 并向城市 33 出发。
  • 77 天,小 W 到达城市 33,获得愉悦值 44 并向城市 11 出发。
  • 1111 天,小 W 到达城市 11,获得愉悦值 11 并结束旅行。
  • 小 W 在该旅行中获得的愉悦值之和为 1313

此外,精灵王国会在不同的时间举办 kk 次美食节。具体来说,第 ii 次美食节将于第 tit_i 天在城市 xix_i 举办,若小 W 第 tit_i 天时恰好在城市 xix_i,那么他在品尝城市 xix_i 的美食时会额外得到 yiy_i 的愉悦值。现在小 W 想请作为精灵王国接待使者的你帮他算出,他在旅行中能获得的愉悦值之和的最大值

输入格式

从文件 delicacy.in 中读入数据。

第一行四个整数 n,m,T,kn, m, T, k,依次表示城市数、道路条数、旅行天数与美食节次数。

第二行 nn 个整数 cic_i,表示每座城市的美食所能提供的愉悦值。

接下来 mm 行每行三个整数 ui,vi,wiu_i, v_i, w_i,依次表示每条道路的起点、终点与通行天数。

最后 kk 行每行三个整数 ti,xi,yit_i, x_i, y_i,依次表示每次美食节的举办时间、举办城市与提供的额外愉悦值。

本题中数据保证:

  • 对所有 1im1\le i\le m,有 uiviu_i \neq v_i。但数据中可能存在路线重复的单向道路,即可能存在 1i<jm1\le i < j\le m,使得 ui=uj,vi=vju_i = u_j, v_i = v_j
  • 对每座城市都满足:至少存在一条以该城市为起点的单向道路。
  • 每次美食节的举办时间 tit_i 互不相同。

输出格式

输出到文件 delicacy.out 中。

仅一行一个整数,表示小 W 通过旅行能获得的愉悦值之和的最大值。

小 W 无法在第 TT 天回到城市 11,则输出 1-1

3 4 11 0
1 3 4
1 2 1
2 1 3
2 3 2
3 1 4
13
4 8 16 3
3 1 2 4
1 2 1
1 3 1
1 3 2
3 4 3
2 3 2
3 2 1
4 2 1
4 1 5
3 3 5
1 2 5
5 4 20
39

数据范围与提示

对于所有测试点:

1n501\le n\le 50nm501n\le m\le 5010k2000\le k\le 2001tiT1091\le t_i\le T\le 10^9

1wi51\le w_i\le 51ci525011\le c_i\le 525011ui,vi,xin1\le u_i, v_i, x_i\le n1yi1091\le y_i\le 10^9

每个测试点的具体限制见下表:

测试点编号 nn mm TT 特殊限制
141\sim 4 5\le 5 50\le 50 5\le 5
585\sim 8 50\le 50 52501\le 52501
9109\sim 10 109\le 10^9 A
111311\sim 13 k=0k=0
141514\sim 15 k10k\le 10
161716 \sim 17
182018 \sim 20 501\le 501

特殊限制 A:n=mn = mui=i,vi=(imodn)+1u_i = i, v_i = (i \bmod n) + 1