给定一个由 $n$ 行数字组成的数字梯形如下图所示。梯形的第一行有 $m$ 个数字。从梯形的顶部的 $m$ 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。

分别遵守以下规则：

1. 从梯形的顶至底的 $m$ 条路径互不相交；
2. 从梯形的顶至底的 $m$ 条路径仅在数字结点处相交；
3. 从梯形的顶至底的 $m$ 条路径允许在数字结点相交或边相交。

一个餐厅在相继的 $n$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾。餐厅可以购买新的餐巾，每块餐巾的费用为 $P$ 分；或者把旧餐巾送到快洗部，洗一块需 $M$ 天，其费用为 $F$ 分；或者送到慢洗部，洗一块需 $n$ 天，其费用为 $S$ 分（$S < F$）。

每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $n$ 天中餐巾使用计划,使总的花费最小。

众所周知，最小费用最大流向来是一个算法很多的问题，下面总结了几个常用的最小费用最大流算法。

美食节共有 $n$ 种不同的菜品，每个同学都点了一份在这 $n$ 个菜品中的菜。总共有 $m$ 个厨师来制作这些菜品。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。第 $j$ 个厨师制作第 $i$ 种菜品的时间记为 $t _ {i,j}$ 。每个同学的等待时间为所有厨师开始做菜起，到自己那份菜品完成为止的时间总长度。总等待时间为所有同学的等待时间之和。

已知共有 $n$ 种菜品，第 $i$ 种菜品需要做 $p_i$ 份，共有 $m$ 个厨师。请计算出最小的总等待时间是多少。

有一个 $n$ 行 $m$ 列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第 $i$ 行第 $j$ 列的格子只能参与 $m _ {i,j}$ 次交换。

输出仅一行，为最小交换总次数。如果无解，输出 $-1$ 。

你的公司需要提供 $n$ 类产品，其中第 $i$ 类产品共需要 $C _ {i}$ 件。公司共有 $m$ 名员工。员工能够制造的产品种类有所区别，我们用一个由 $0$ 和 $1$ 组成的 $m\times n$ 的矩阵 $\mathbb {A}$ 来描述每名员工能够制造哪些产品。

对于员工 $i$ ，给出 $S_i$ 。定义他的愤怒值与他制作的产品数量之间的函数是一个 $S_i+1$ 段的分段函数。设 $T _ {i,0}=0$,$T _ {i,S _ {i+1}}=+\infty$ ，那么当他制造第 $[T _ {i,j-1}+1,T _ {i,j}]$ 件产品时，每件产品会使他的愤怒值增加 $W _ {i,j}$ ， $1\leq j\leq S _ {i+1}$ 。保证 $0<W _ {i,j} < W _ {i,j+1}, ; 0 < T _ {i,j} < T _ {i,j+1}$ 。

你的任务是制定出一个产品的分配方案，使得订单条件被满足，并且所有员工的愤怒值之和最小。

给定一张有向图，每条边都有一个容量 $C$ 和一个扩容费用 $W$ 。这里扩容费用是指将容量扩大 $1$ 所需的费用。

现在请你编写一个程序求出：

1. 在不扩容的情况下， $1$ 到 $N$ 的最大流；
2. 将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。