题目描述

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

有 $n$ 个实数变量 $x_1,x_2,\dots,x_n$ 和 $m$ 条约束，其中第 $i$ 条约束形如 $\sum_{j=1}^n a_{i,j}x_j \le b_i$。

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

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

保证数据随机。

输入格式

第一行两个正整数 $n,m$。

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

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

输出格式

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

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

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

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

判断第二行是否合法时，我们首先检验 $F$ 与 $\sum_{j=1}^n c_j x_j$ 的相对误差或绝对误差不超过 $10^{-6}$，再对于所有 $i$，检验 $\sum_{j=1}^n a_{i,j}x_j\le b_i$ 或 $\sum_{j=1}^n a_{i,j}x_j$ 与 $b_i$ 的相对误差或绝对误差不超过 $10^{-6}$。若均满足，则判为正确。

如果出现 Infeasible 或 Unbounded 时，不需要输出第二行。

2 2
1 1
2 1 6
-1 2 3

4.2
1.8 2.4

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

4.0
4.0 0.0

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

Infeasible

2 1
0 1
1 0 1

Unbounded

提示

数据范围

对于所有数据，$1\leq n,m \leq 100$，$0 \leq |a_{i,j}|,|b_i|,|c_j|\leq 100$。保证数据随机。

子任务编号	$n,m\le$	特殊性质	分值
1	$10$		$20$
2	$20$
3	$50$	$b_i\ge 0$	$10$
4			$20$
5	$100$		$30$