分数: 400 分
问题陈述
高桥正在参加一场集会,经过 N 城市。城市已编号 1 通过 N.
这次集会发生于 K 天,从第 1 天到第 1 天 K。高桥每天只呆在一个城市。第一天,他可以选择并留在任何一个 N 城市。从第二天开始,他从前一天停留的城市通过旅行路线移动到另一个城市,并在那里停留。
有 M 城市之间提供出行路线,全部为单程。的 k- 第条路线代表从城市出发的旅行 a_k 前往城市 b_k。使用这条路线可以让他留在城市 b_k 留在城市的第二天 a_k (不一定可以反向行驶)。可以保证 每条路线的 a_k \neq b_k 。
从第2天开始,他只能移动到有从前一天停留的城市出发的旅行路线的城市。由于没有到同城的自环,所以他不能在同一个城市连续停留两天。但是,他可以再次留在同一城市以及中间的其他城市。
各城市 i 有一个基本分数 P_i。居住城市获得的分数 i 当天 j (1 \leq j \leq K) 是 (P_i \times j) \bmod Q。在这里, Q 是给定的正整数,并且 \bmod 表示非负余数。
A 入住计划 为 K days 是长度为城市数字的序列 K, c_1, c_2, \ldots, c_K,满足以下所有条件:
- 每个 c_j (1 \leq j \leq K) 是介于 1 和 N,包含在内(同一城市号码可能在序列中出现多次)。
- 对于所有 1 \leq j \leq K - 1,存在一条从城市出发的出行路线 c_j 前往城市 c_{j+1}.
请最大化总分 K 天,即:
\sum_{j=1}^{K} \bigl((P_{c_j} \times j) \bmod Q\bigr)
查找所有有效住宿计划中该金额的最大值。
保证至少存在一个有效的入住计划。
约束
- 1 \leq N \leq 1000
- 0 \leq M \leq \min(N \times (N - 1),\; 50000)
- 1 \leq K \leq 1000
- 1 \leq Q \leq 10^6
- 0 \leq P_i \leq 10^6 (1 \leq i \leq N)
- 1 \leq a_k, b_k \leq N (1 \leq k \leq M)
- a_k \neq b_k (1 \leq k \leq M)
- 没有重复的旅行路线(即所有 (a_k, b_k) 是不同的)。
- 至少有一个有效的入住计划。
- 所有输入值均为整数。
输入
N M K Q P_1 P_2 \ldots P_N a_1 b_1 a_2 b_2 \vdots a_M b_M
- 第一行包含城市数量 N,出行路线数量 M, 反弹天数 K,以及正整数 Q 用于分数计算,以空格分隔。
- 第二行包含城市的基本分数 P_1, P_2, \ldots, P_N,以空格分隔。
- 的 k- 以下各项 M 行 (1 \leq k \leq M) 包含 a_k 和 b_k 以空格隔开,代表有一条从城市出发的单程出行路线 a_k 前往城市 b_k。如果 M = 0,此部分为空。
输出
打印超过的最大总分 K 天在一行。
示例输入 1
3 3 4 10 2 5 7 1 2 2 3 3 1
示例输出 1
24
示例输入 2
4 5 3 13 4 9 1 7 1 2 1 3 2 4 3 4 4 1
示例输出 2
22
示例输入 3
8 14 10 97 3 14 159 26 535 897 932 38 1 2 1 3 2 4 3 4 4 5 5 6 6 4 5 7 7 8 8 5 2 6 3 7 6 8 8 1
示例输出 3
606
示例输入 4
15 35 25 1000000 0 999999 123456 789012 345678 901234 567890 234567 890123 456789 111111 222222 333333 444444 555555 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 1 1 5 1 8 2 6 2 9 3 1 3 7 4 8 4 12 5 9 5 13 6 10 6 14 7 11 7 15 8 12 8 1 9 13 9 2 10 14 10 3
示例输出 4
20223100
示例输入 5
1 0 1 1 0
示例输出 5
0