Description

Hanako 是一家拥有两名员工的小公司的 CEO。目前她有一些任务，希望通过让员工完成任务来赚取利润。员工可以通过任务提升技能，而更高的技能可以从同一任务中获得更大的利润。因此，以适当的顺序将任务分配给合适的员工，对于最大化总利润至关重要。

对于员工 $i$ 和任务 $j$ 的每一对组合 $(i, j)$，定义了两个非负整数 $v_{i,j}$ 和 $s_{i,j}$。其中，$v_{i,j}$ 是任务适配度，$s_{i,j}$ 是技能成长量。当技能点为 $p$ 的员工 $i$ 完成了任务 $j$ 时，会获得 $p \times v_{i,j}$ 的利润，并且他的技能点增加至 $p + s_{i,j}$。初始时，两名员工的技能点均为 $p_0$。

注意，技能点是独立的，一名员工完成任务不会改变另一名员工的技能点。每个任务只能由一名员工完成一次。任务的执行顺序可以任意选择。

Input Format

输入由单个测试用例组成，格式如下。

$$\begin{aligned} &n \ p_0\\ &s_{1,1} \ \cdots \ s_{1,n}\\ &s_{2,1} \ \cdots \ s_{2,n}\\ &v_{1,1} \ \cdots \ v_{1,n}\\ &v_{2,1} \ \cdots \ v_{2,n}\\ \end{aligned}$$

所有输入项均为非负整数。任务数量 $n$ 满足 $1 \leq n \leq 100$。初始技能点 $p_0$ 满足 $0 \leq p_0 \leq 10^8$。每个 $s_{i,j}$ 是员工 $i$ 完成任务 $j$ 后的技能成长量，满足 $0 \leq s_{i,j} \leq 10^6$。每个 $v_{i,j}$ 是员工 $i$ 对任务 $j$ 的任务适配度，满足 $0 \leq v_{i,j} \leq 10^6$。

Output Format

在一行中输出可能的最大总利润。

4 0
10000 1 1 1
1 1 10000 1
1 10000 1 1
1 1 1 10000

200000000

3 1
1 1 1
2 2 2
2 2 2
1 1 1

12

Hint

翻译由 DeepSeek V3 完成