题目描述

Hanako is the CEO of a small company with two employees. She currently has some number of tasks and aims to earn some profits by making the employees do the tasks. Employees can enhance their skills through the tasks and, with higher skills, a larger profit can be earned from the same task. Thus, assigning tasks to appropriate employees in an appropriate order is important for maximizing the total profit.

For each pair $(i, j)$ of employee $i$ and task $j$, two non-negative integers $v_{i,j}$ and $s_{i,j}$ are defined. Here, $v_{i,j}$ is the task compatibility and $s_{i,j}$ is the amount of skill growth. When task $j$ has been completed by employee $i$ whose skill point was $p$, a profit of $p \times v_{i,j}$ is earned, and his skill point increases to $p + s_{i,j}$. Initially, both employees have skill points of $p_0$.

Note that the skill points are individual, and completing a task by one employee does not change the skill point of the other. Each task must be done only once by only one employee. The order of tasks to carry out can be arbitrarily chosen.

输入格式

The input consists of a single test case of the following 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}$$

All the input items are non-negative integers. The number of tasks $n$ satisfies $1 \leq n \leq 100$. The initial skill point $p_0$ satisfies $0 \leq p_0 \leq 10^8$. Each $s_{i,j}$ is the amount of skill growth for the employee $i$ by completing the task $j$, which satisfies $0 \leq s_{i,j} \leq 10^6$. Each $v_{i,j}$ is the task compatibility of the employee $i$ with the task $j$, which satisfies $0 \leq v_{i,j} \leq 10^6$.

输出格式

Output the maximum possible total profit in one line.

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