Task Assignment to Two Employees

Hanako is the CEO of a small company with two employees. She currently has $n$ tasks and wants to earn profits by having the employees do them. Employees can build their skills through tasks, and with higher skill points, they earn a larger profit from the same task. Assigning tasks to the right employee in the right order is therefore important for maximizing the total profit.

For each pair $(i, j)$ of employee $i$ and task $j$, there are two non-negative integers $v_{i,j}$ and $s_{i,j}$. Here, $v_{i,j}$ is the task compatibility, and $s_{i,j}$ is the amount of skill growth. When employee $i$ with skill point $p$ completes task $j$, the employee earns a profit of $p \times v_{i,j}$, and the skill point increases to $p + s_{i,j}$. Initially, both employees have skill point $p_0$.

Skill points are tracked separately for each employee. When one employee completes a task, the other employee's skill point does not change. Each task must be done exactly once by exactly one employee. You can choose the order of the tasks freely.

The input consists of a single test case in the following format.

$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}$

All input values are non-negative integers. The number of tasks $n$ satisfies $1 \le n \le 100$. The initial skill point $p_0$ satisfies $0 \le p_0 \le 10^8$. Each $s_{i,j}$ satisfies $0 \le s_{i,j} \le 10^6$, and each $v_{i,j}$ satisfies $0 \le v_{i,j} \le 10^6$.

Output the maximum possible total profit on one line.