该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

自从Sanhai研究了流量网络上次，访问的人越来越多， 于是Sanhai研究了更高级的网络

在 Sanhai 的全球分层供需网络中：

• 节点可能是数据生产者（数据中心）、消费者（用户终端）、或中转枢纽；
• 链路可能是光纤、卫星、跨洋电缆或虚拟专线，每条链路都有容量上限与单位费用；
• 费用可能为负，表示存在补贴机制，但保证无负环。

此外，每个节点 $v$ 有一个净需求值 $b_v$：

• $b_v > 0$：该节点至少需要 $b_v$ 单位数据；
• $b_v < 0$：该节点必须输出 $|b_v|$ 单位数据；
• $b_v = 0$：该节点仅作为中转。

系统要求：

• 必须找到一条可行流，满足所有节点的净需求约束；
• 在所有可行流中，总费用最小；
• 若无解，输出 -1。

---

数学建模

决策变量

对每条边 $(u,v)$ 定义流量变量：

$$f(u,v) \geq 0$$

约束条件

1. 容量约束

$$0 \leq f(u,v) \leq cap(u,v), \quad \forall (u,v) \in E $$

2. 流量守恒约束
   对每个节点 $v$：

$$\sum_{(u,v)\in E} f(u,v) - \sum_{(v,w)\in E} f(v,w) = b_v $$

3. 供需平衡

$$\sum_{v=1}^n b_v = 0$$

目标函数

最小化总费用：

$$\min \sum_{(u,v)\in E} f(u,v) \cdot cost(u,v)$$

---

输入格式

n m
u1 v1 cap1 cost1
...
um vm capm costm
b1 b2 ... bn

• 第一行：
  • $n$ —— 节点数（$1 \le n \le 500$）
  • $m$ —— 有向边数（$0 \le m \le 10^4$）
• 接下来 $m$ 行：每行四个整数
  • $u_i, v_i$ —— 边的起点和终点
  • $cap_i$ —— 容量（$0 \le cap_i \le 10^9$）
  • $cost_i$ —— 单位费用（$-10^4 \le cost_i \le 10^4$）
• 最后一行：$n$ 个整数，表示每个节点的净需求 $b_v$
  • $\sum b_v = 0$ 保证供需平衡

---

输出格式

minCost

• 若不存在可行流，输出 -1；
• 否则输出最小费用。

---

样例输入

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

样例输出

13

---

数据范围

• $1 \le n \le 500$
• $0 \le m \le 10^4$
• 容量范围：$0 \le cap \le 10^9$
• 费用范围：$-10^4 \le cost \le 10^4$
• 节点净需求 $b_v$ 的绝对值不超过 $10^9$，并且 $\sum b_v = 0$
• 保证无负环