这是一道模板题。
有 $n$ 个萌萌哒节点，它们之间由 $m$ 条萌萌哒的有向边连接起来。每条边五种属性，可表示成五元组 $(a, b, lower, upper, cost)$，表示这是一条从节点 $a$ 连向节点 $b$ 的有向边（节点编号为 $1$ 到 $n$），其流量要限制在 $[lower, upper]$ 之间，在这条边上单位流量会造成 $cost$ 的代价。
现在，你要给每条萌萌哒的有向边安排一个流量，使得所有边上的流量都满足对应边的性质并且满足所有点流量平衡。
形式化地，令萌萌哒点集为 $V$，萌萌哒边集为 $E$，萌萌哒边 $e$ 上你安排的流量为 $flow_e$。则对于 $∀e \in E$ 满足 $flow_e \in [lower_e, upper_e]$；且 $∀u \in V$，满足 $\sum_{(v, u) \in E}{flow_{(v, u)}} = \sum_{(u, v) \in E}{flow_{(u, v)}}$。注意以上边均简用二元组 $(a, b)$ 表示，对应着五元组前两维，后三维任意。
输入格式
第一行两个正整数 $n$ 和 $m$。
接下来 $m$ 行每行五个整数 $a, b, lower, upper, cost$，描述一条边。
输出格式
一个整数表示最小费用。如果不存在可行流，请输出卖萌表情 QAQ。
样例一
input
6 10
1 2 2 5 5
2 3 3 9 -3
1 4 0 9 2
2 4 1 10 10
3 4 0 9 5
4 5 2 7 8
5 3 3 7 6
3 6 2 5 3
5 6 1 8 10
6 1 5 10 1output
110样例二
input
6 9
1 2 2 5 5
2 3 3 9 -3
1 4 0 9 2
2 4 1 10 10
3 4 0 9 5
4 5 2 7 8
5 3 3 7 6
3 6 2 5 3
5 6 1 8 10output
QAQ样例三
见样例数据下载
限制与约定
| 子任务编号 | 分值 | $n$ | $m$ | 满足性质 |
|---|---|---|---|---|
| 1 | $10$ | $\le 10$ | $\le 20$ | - |
| 2 | $9$ | $\le 300$ | $\le 800$ | $1、2$ |
| 3 | $25$ | $\le 300$ | $\le 800$ | $1$ |
| 4 | $25$ | $\le 300$ | $\le 800$ | $2$ |
| 5 | $31$ | $\le 300$ | $\le 800$ | - |
性质 $1$：保证对于 $∀e \in E$，有 $low_e = 0$。
性质 $2$：保证对于 $∀e \in E$，有 $cost_e \ge 0$。
对于所有数据，保证 $∀e \in E$，有 $a_e, b_e \in [1, n]$，$0 \le lower_e \le upper_e \le 300000$，$|cost_e| \le 100000$。
时间限制：$10\texttt{s}$
空间限制：$512\texttt{MB}$
