题目背景

在 Sanhai 全球数据调度体系中，存在一张跨越多大洲的通信网络。

• 每个节点可能代表一个数据中转枢纽（如洲际交换中心）、区域路由器、边缘服务器，或最终的用户终端。
• 链路不仅仅是“光纤”或“卫星通道”，还可能是跨洋电缆、量子通信信道，甚至是临时租用的虚拟专线。

在这张网络中，数据的传输受到以下多重约束：

1. 容量限制：每条链路都有最大可承载的数据量，超过即会导致拥塞或丢包。
2. 能量/费用消耗：每单位数据通过链路时会产生能量损耗或费用支出，部分链路甚至可能因为补贴而带来负费用。
3. 需求上界：每个用户终端节点有一个最大可接收量（可能无限大），表示该用户的带宽上限或需求上限。

Sanhai 的目标是：

• 从唯一的生产节点（编号为 1，代表核心服务器）出发，
• 通过复杂的多层级网络，
• 向所有用户终端分配数据流量。

他需要知道：

1. 最大可行总吞吐量 —— 在所有约束下，系统最多能将多少数据从源点传递到用户终端；
2. 最小能量消耗 —— 在达到该最大吞吐量的前提下，系统所需的最小费用。

请注意：

• 网络中可能存在负费用链路，但保证不存在负环；
• 用户需求值仅作为上界，不要求必须完全满足；
• 你需要在所有可能的流量分配方案中，找到最优解。

题目描述

给定一个有向图：

• 节点 $1$ 是唯一的生产节点；
• 有 $k$ 个消费节点，每个消费节点有一个最大需求值；
• 每条边有容量与单位费用。

请计算：

• 系统的最大总吞吐量；
• 在该吞吐量下的最小总费用。

输入格式

n m k
u1 v1 cap1 cost1
...
um vm capm costm
id1 demand1
...
idk demandk

• 第一行：
  • $n$ —— 节点数（$1 \le n \le 500$）
  • $m$ —— 有向边数（$0 \le m \le 10^4$）
  • $k$ —— 消费节点数量
• 接下来 $m$ 行：每行四个整数
  • $u_i, v_i$ —— 边的起点和终点
  • $cap_i$ —— 容量（$0 \le cap_i \le 10^9$）
  • $cost_i$ —— 单位费用（$-10^4 \le cost_i \le 10^4$）
• 接下来 $k$ 行：每行两个整数
  • $id_j$ —— 消费节点编号
  • $demand_j$ —— 最大需求量（可为无穷大）

输出格式

maxFlow minCost

• maxFlow：最大总吞吐量
• minCost：在该吞吐量下的最小费用

样例输入

4 5 2
1 2 2 2
1 3 1 5
2 3 1 1
2 4 1 3
3 4 2 2
4 5
3 3

样例输出

5 27

数据范围与提示

• $1 \le n \le 500$
• $0 \le m \le 10^4$
• 容量与费用范围如上
• 保证无负环