CF1383F.Special Edges

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 that goes from node $1$ to node $n$ after each such query?

Help her!

考拉熊 Koa 有一张有向图 $G$，包含 $n$ 个节点和 $m$ 条边。每条边都具有一个容量。图中恰好有 $k$ 条边是特殊的（编号从 $1$ 到 $k$），这些特殊边的初始容量均为 $0$。

Koa 向你提出 $q$ 个查询。在每个查询中，她给出 $k$ 个整数 $w_1, w_2, \ldots, w_k$，表示第 $i$ 条特殊边的容量变为 $w_i$（其余边的容量保持不变）。

Koa 想知道：每次这样的查询之后，从节点 $1$ 到节点 $n$ 的最大流是多少？

请帮帮她！

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.

输入的第一行包含四个整数 $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$），分别表示节点数、边数、特殊边数以及查询次数。

接下来的 $m$ 行，每行包含三个整数 $u$、$v$、$w$（$1 \le u, v \le n$；$0 \le w \le 25$），表示一条从节点 $u$ 指向节点 $v$ 的有向边，其容量为 $w$。

边按输入顺序从 $1$ 开始编号。前 $k$ 条边为特殊边。保证对所有满足 $1 \le i \le k$ 的 $i$，均有 $w_i = 0$。

接下来的 $q$ 行，每行包含 $k$ 个整数 $w_1, w_2, \ldots, w_k$（$0 \le w_i \le 25$），表示一次查询。其中 $w_i$ 表示第 $i$ 条边的容量。

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.

对于第 $i$ 个查询，输出一个整数 $res_i$ —— 在第 $i$ 个查询所指定的特殊边权重下，从节点 $1$ 到节点 $n$ 能获得的最大流。

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$.

对于第二个样例，以下图片分别对应前两个查询（从左到右）。每条边上标有一对数值“流量/容量”，分别表示经该边推送的流量及该边的容量。特殊边以红色标出。

如图所示，第一个查询中从节点 $1$ 到节点 $4$ 的最大流为 $0$，第二个查询中则为 $1$。