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](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.

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