30935번 - Task Assignment to Two Employees 다국어

문제

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.

$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 the input items are non-negative integers. The number of tasks $n$ satisfies 1ドル ≤ n ≤ 100$. The initial skill point $p_0$ satisfies 0ドル ≤ p_0 ≤ 10^8$. Each $s_{i,j}$ is the amount of skill growth for the employee $i$ by completing the task $j,ドル which satisfies 0ドル ≤ s_{i,j} ≤ 10^6$. Each $v_{i,j}$ is the task compatibility of the employee $i$ with the task $j,ドル which satisfies 0ドル ≤ v_{i,j} ≤ 10^6$.

출력

Output the maximum possible total profit in one line.

제한

힌트