题目描述Description

深圳技术大学校园内共有 n 个地点，编号为 1,2,\ldots,n，例如教学楼、实验楼、图书馆、宿舍区、运动场等。校园内有 m 条双向道路连接这些地点。

第 i 条道路连接地点 x_i 与 y_i，通过该道路需要消耗 w_i 点通行代价。每个地点 i 都有一个科创值 a_i。

为了保障校园高峰期通行效率，学校需要先对所有双向道路进行单向通行管制。也就是说，每条道路都必须被定向成两个方向之一。

对于每个地点 v，给定两个整数 L_v,U_v。若一种道路定向方案中，地点 v 的出边数量为 \operatorname{outdeg}(v)，则该方案合法，当且仅当所有地点 v 都满足 L_v \le \operatorname{outdeg}(v) \le U_v。

若不存在任何合法定向方案，则认为不存在可行的校园通行路线。

对于一条双向道路 (u,v)，如果存在至少一种合法定向方案，使得该道路的方向为 u \to v，则称 u \to v 是一条 可行通道。

注意，同一条双向道路可能只对应一个可行通道，也可能同时对应 u \to v 和 v \to u 两个可行通道。

设原无向图中地点 v 的度数为 \deg(v)。对于每一个在图中出现过的度数 d，定义 cnt_d=|\{v\mid \deg(v)=d\}|，即度数为 d 的地点数量。

对于两个出现过的度数 d_1,d_2，定义偏序关系 d_1 \preceq d_2，当且仅当满足以下条件之一：

1. d_1=d_2；
2. d_1>0，d_2 能被 d_1 整除，且 cnt_{d_1}\le cnt_{d_2}。

如果所有出现过的度数类可以被划分成不超过 B 条链，则称该校园道路网络满足 层级有序性。

一条链指的是若干个度数类构成的序列 d_{p_1},d_{p_2},\ldots,d_{p_t}，满足 d_{p_1}\preceq d_{p_2}\preceq \cdots \preceq d_{p_t}。

如果校园道路网络不满足层级有序性，也认为不存在可行的校园通行路线。

一条校园通行路线是一个地点序列 v_1,v_2,\ldots,v_c，满足：

1. c\ge 1；
2. 所有地点互不相同；
3. 对于每个 1\le i<c，必须存在一条可行通道，且方向为 v_i\to v_{i+1}。

路线的通行代价为经过道路的权值之和。若 c=1，则通行代价为 0。

路线的科创总值为 a_{v_1}+a_{v_2}+\cdots+a_{v_c}。

给定正整数 k。如果一条校园通行路线的科创总值恰好是 k 的倍数，则称其为 智行路线。

请你求出通行代价最小的智行路线。若不存在这样的路线，输出 -1。

输入格式Input

第一行输入一个整数 T，表示测试数据组数。

对于每组测试数据：

第一行输入四个整数 n,m,k,B，分别表示地点数、道路数、模数以及层级有序性的链数限制。

第二行输入 n 个整数 a_1,a_2,\ldots,a_n，表示每个地点的科创值。

接下来 n 行，每行输入两个整数 L_i,U_i，表示地点 i 的出度上下界。

接下来 m 行，每行输入三个整数 x_i,y_i,w_i，表示第 i 条双向道路连接地点 x_i 与地点 y_i，道路权值为 w_i。

输出格式Output

对于每组测试数据，输出一行一个整数。

若存在满足条件的智行路线，输出其最小通行代价；否则输出 -1。

样例Sample

提示Hint

样例解释

第一组数据中，只有一种合法定向方案：1\to2\to3。

因此 1\to2 和 2\to3 都是可行通道。路线 1\to2\to3 的科创总值为 1+1+1=3，是 3 的倍数，总代价为 5+7=12，因此答案为 12。

第二组数据中，地点 1 的科创值为 0，单独选择地点 1 就是一条智行路线，代价为 0。

第三组数据中，唯一一条道路必须被定向，但两个地点的出度上界均为 0，不存在任何合法定向方案，因此输出 -1。

数据范围

• 1\le T\le 5
• 2\le n\le 10^5
• 1\le m\le 10^5
• 2\le k\le 6
• 1\le B\le n
• 0\le a_i<k
• 0\le L_i\le U_i\le n-1
• 1\le x_i,y_i\le n
• x_i\ne y_i
• 1\le w_i\le 10^9

保证每组数据中的无向图无自环、无重边。

保证所有测试数据满足：

• \sum n\le 2\times 10^5
• \sum m\le 2\times 10^5

NOTE

由于OJ限制，本题存在一定的卡常情况，需要比较优秀的写法才能AC。

可以试试O3:

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

关于递归深度的特别说明

本题递归深度可能引发栈溢出。为了避免因递归过深而 RE，你可以参考下面这种方式：

int main() {
    int size(64 << 20);  // 64 MB
    __asm__("movq %0, %%rsp\n" :: "r"((char*)malloc(size) + size));
    // your code ...
    exit(0);   // 必须使用 exit 结束程序，不能通过 return 返回
}

出题Author

Ldawn_AI

来源Source

深圳技术大学第六届程序设计竞赛