题目描述

给定一张 $n$ 个点 $m$ 条边的有向图，其中源点为 $s$ 点，终点为 $t$ 点。每条边有起点 $a_i$，终点 $b_i$，流量下界 $l_i$，流量上界 $u_i$，费用 $c_i$。

现在，你需要找到一个从 $s$ 到 $t$ 的流，满足每个点的流量平衡与每条边的流量上下界，且在流量最大的情况下费用尽可能小。

输入格式

输入的第一行包含四个整数 $n, m, s, t$。

接下来 $m$ 行，每行包含五个整数 $a_i, b_i, l_i, u_i, c_i$。

输出格式

如果不存在合法流，则输出一行一个整数 -1。

否则，输出一行两个整数，第一个整数表示最大流量，第二个整数表示在流量最大的情况下的最小费用。

样例数据

样例 1 输入

3 3 1 3
1 2 0 6 0
2 3 1 1000 4
2 3 0 1000 3

样例 1 输出

6 19

样例 2 输入

5 6 2 4
2 1 1 6 4
2 3 0 5 1
1 3 2 8 2
3 4 1 7 1
3 5 0 4 1
5 4 1 5 2

样例 2 输出

11 60

样例 3 输入

3 1 1 3
2 3 1 100 -100

样例 3 输出

-1

样例 4 输入

7 21 6 2
4 2 5838 564426 865577
2 4 138826 402418 671157
3 2 123701 426813 -543072
4 7 98453 297069 -986761
4 1 21240 326890 -393845
6 7 2698 993886 -59647
4 6 82877 385922 -912546
7 4 25734 366246 285364
7 1 69448 399825 -401006
3 6 22302 805072 919199
6 3 124308 353738 -384169
3 5 139305 535596 -570512
5 2 81261 479615 -662499
4 2 17109 716121 -195178
7 3 7838 518193 274351
6 4 60957 638462 -423334
7 2 56175 606681 -703583
6 3 35947 112359 -495175
1 3 90688 695522 618674
6 3 26527 999630 -429406
5 7 58044 610148 862096

样例 4 输出

2313184 -1814133530696

提示

对于所有数据，保证 $1 \le n \le 1\,000$，$1 \le m \le 5\,000$，$1 \le s,t \le n$，$s \ne t$。

对于所有数据，保证 $1 \le a_i, b_i \le n$，$a_i \ne b_i$，$1 \le l_i \le u_i \le 10^6$，$-10^6 \le c_i \le 10^6$。

特别地，保证本题的数据通过以下方式随机生成：

1. 选定 $n$，$m$，$s$，$t$ 的值，不保证 $n,m,s,t$ 随机生成。
2. 通过以下方式生成一张 $m$ 条边的有向图 $G$：
   1. 选定参数 $k_1, k_2$，满足 $0 \le k_1, k_2$ 且 $k_1 + k_2 \le n$。
   2. 进行 $k_1$ 次：
      • 均匀随机选择 $1 \le a \le n$ 且 $a \ne s$，添加边 $s \to a$。
   3. 进行 $k_2$ 次：
      • 均匀随机选择 $1 \le a \le n$ 且 $a \ne t$，添加边 $a \to t$。
   4. 进行 $m-k_1-k_2$ 次：
      • 均匀随机地选择 $1 \le a, b \le n$ 且 $a \ne b$，添加边 $a \to b$。
3. 对于每条边，均匀随机地选择其费用 $c_i \in [-10^6, 10^6]$。
4. 对于每条边，选择一个 $\Delta_i \in [1, 10^6]$，不保证 $\Delta_i$ 随机生成。
5. 随机进行以下过程若干次：
   1. 选择一个值 $\delta \in [1, 10^6]$，不保证 $\delta$ 随机生成。
   2. 从 $s$ 开始 dfs 整张图，每次均匀随机地选择一个出边。
   3. 如果最终到达了点 $t$，则将 $s \to t$ 路径上所有边的 $l_i$ 增加 $\delta$。
   4. 特别地，若存在边的 $l_i$ 超过了 $10^6 - \Delta_i - \delta$，则放弃本轮操作。
6. 随机进行以下过程若干次：
   1. 选择一个值 $\delta \in [1, 10^6]$，不保证 $\delta$ 随机生成。
   2. 均匀随机地选择一个顶点 $x$。
   3. 从 $x$ 开始 dfs 整张图，每次均匀随机地选择一个出边。
   4. 如果最终回到了点 $x$，则将走过的路径上所有边的 $l_i$ 增加 $\delta$。
   5. 特别地，若存在边的 $l_i$ 超过了 $10^6 - \Delta_i - \delta$，则放弃本轮操作。
7. 令每条边的 $u_i = l_i + \Delta_i$。