这是一道模板题。

（这个题现在标程挂了。。哪位哥哥愿意提供一下靠谱的标程呀？） 现在的新标程有没有问题啊？ 现在的新标程有没有问题啊？

已将所有ex tests的t改成1。现在的checker会先判解是否合法，再判和标准答案的误差。如果发现有std优的合法解，请联系管理员。

本题中你需要求解一个标准型线性规划：

有 $n$ 个实数变量 $x_1,x_2,\dots ,x_n$ 和 $m$ 条约束，其中第 $i$ 条约束形如 $\sum _{j=1}^n{a}_{ij}{x}_j\le b_i$。

此外这 $n$ 个变量需要满足非负性限制，即 $x_j\ge 0$。

在满足上述所有条件的情况下，你需要指定每个变量 $x_j$ 的取值，使得目标函数 $F=\sum _{j=1}^n{c}_j{x}_j$ 的值最大。

输入格式

第一行三个正整数 $n,m,t$。其中 $t\in \{0,1\}$。

第二行有 $n$ 个整数 $c_1,c_2,\cdots ,c_n$，整数间均用一个空格分隔。

接下来 $m$ 行，每行代表一条约束，其中第 $i$ 行有 $n+1$ 个整数 $a_{i1},a_{i2},\cdots ,a_{in},b_i$，整数间均用一个空格分隔。

输出格式

如果不存在满足所有约束的解，仅输出一行 "Infeasible"。

如果对于任意的 $M$，都存在一组解使得目标函数的值大于 $M$，仅输出一行"Unbounded"。

否则，第一行输出一个实数，表示目标函数的最大值 $F$。当第一行与标准答案的相对误差或绝对误差不超过 ${10}^{-6}$，你的答案被判为正确。

如果 $t=1$，那么你还需要输出第二行，用空格隔开的 $n$ 个非负实数，表示此时 $x_1,x_2,\dots ,x_n$ 的取值，如有多组方案请任意输出其中一个。

判断第二行是否合法时，我们首先检验 $F-\sum _{j=1}^n{c}_j{x}_j$ 是否为 $0$，再对于所有 $i$，检验 $min\{0,b_i-\sum _{j=1}^n{a}_{ij}{x}_j\}$ 是否为 $0$。检验时我们会将其中大于 $0$ 的项和不大于 $0$ 的项的绝对值分别相加得到 $S_{+}$ 和 $S_{-}$，如果 $S_{+}$ 和 $S_{-}$ 的相对误差或绝对误差不超过 ${10}^{-6}$，则判为正确。

如果 $t=0$，或者出现 Infeasible 或 Unbounded 时，不需要输出第二行。

样例一

input

2 2 1
1 1
2 1 6
-1 2 3

output

4.2
1.8 2.4 

explanation

两条约束分别为 $2x_1+x_2\le 6,-x_1+2x_2\le 3$。

当 $x_1=1.8,x_2=2.4$ 时目标函数 $x_1+x_2$ 取到最大值 $4.2$。

样例二

input

2 2 1
1 -1
1 1 4
-1 -2 -2

output

4.0
4.0 0.0

explanation

注意 $x_j\ge 0$ 的限制。

样例三

input

3 3 1
0 0 1
-2 1 0 -4
1 1 0 4
1 -2 0 -4

output

Infeasible

样例四

input

2 1 1
0 1
1 0 1

output

Unbounded

限制与约定

对于所有数据，$1\le n,m\le 20$，$0\le |a_{ij}|,|b_i|,|c_j|\le 100$，$t\in \{0,1\}$。

本题包含 4 个子任务，每个 25 分。

子任务 1,3 满足 $b_i\ge 0$。

子任务 2,4 没有特殊限制。

子任务 1,2 中 $t=0$。

子任务 3,4 中 $t=1$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载