Special Edges

题意翻译

给定一张 $n$ 个顶点，$m$ 条边的有向图 $G$，其中每条边有一个非负整数的容量。其中有 $k$ 条边是特殊的，它们在原图中的编号为 $1$ 到 $k$。在初始情况下它们的容量均为 $0$。 现在有 $q$ 组询问，对于每组询问，会给定 $k$ 个非负整数 $w_1, w_2, \ldots, w_k$，你需要求出：如果将编号为 $i$ 的特殊边的容量改为 $w_i$ (对 $i=1,2,\ldots,k$)，那么从 $1$ 到 $n$ 的最大流会是多少？

题目描述

Koa the Koala has a directed graph $ G $ with $ n $ nodes and $ m $ edges. Each edge has a capacity associated with it. Exactly $ k $ edges of the graph, numbered from $ 1 $ to $ k $ , are special, such edges initially have a capacity equal to $ 0 $ . Koa asks you $ q $ queries. In each query she gives you $ k $ integers $ w_1, w_2, \ldots, w_k $ . This means that capacity of the $ i $ -th special edge becomes $ w_i $ (and other capacities remain the same). Koa wonders: what is the [maximum flow](https://en.wikipedia.org/wiki/Maximum_flow_problem#Definition) that goes from node $ 1 $ to node $ n $ after each such query? Help her!

输入输出格式

输入格式

The first line of the input contains four integers $ n $ , $ m $ , $ k $ , $ q $ ( $ 2 \le n \le 10^4 $ , $ 1 \le m \le 10^4 $ , $ 1 \le k \le \min(10, m) $ , $ 1 \le q \le 2 \cdot 10^5 $ ) — the number of nodes, the number of edges, the number of special edges and the number of queries. Each of the next $ m $ lines contains three integers $ u $ , $ v $ , $ w $ ( $ 1 \le u, v \le n $ ; $ 0 \le w \le 25 $ ) — the description of a directed edge from node $ u $ to node $ v $ with capacity $ w $ . Edges are numbered starting from $ 1 $ in the same order they are listed in the input. The first $ k $ edges are the special edges. It is guaranteed that $ w_i = 0 $ for all $ i $ with $ 1 \le i \le k $ . Each of the next $ q $ lines contains $ k $ integers $ w_1, w_2, \ldots, w_k $ ( $ 0 \le w_i \le 25 $ ) — the description of the query. $ w_i $ denotes the capacity of $ i $ -th edge.

输出格式

For the $ i $ -th query, print one integer $ res_i $ — the maximum flow that can be obtained from node $ 1 $ to node $ n $ given the $ i $ -th query's special edge weights.

输入输出样例

输入样例 #1

2 1 1 3
1 2 0
0
1
2

输出样例 #1

0
1
2

输入样例 #2

4 4 2 5
1 2 0
2 3 0
2 4 5
3 4 2
0 0
1 10
10 0
7 1
7 2

输出样例 #2

0
1
5
6
7

说明

For the second sample, the following images correspond to the first two queries (from left to right respectively). For each edge there is a pair flow/capacity denoting flow pushed through the edge and edge's capacity. The special edges are colored in red. As you can see in first query maximum flow from node $ 1 $ to node $ 4 $ equals $ 0 $ and in second query equals $ 1 $ .