Contest Strategy

Time limit2sMemory limit1024 MB

Summary

Given three chains of subtasks with points and solve times, find the maximum total score achievable within time T when each problem's subtasks must be solved in order.

Level: Hard10 of 10
Topics: Dynamic programming, Divide and conquer, Prefix sum
Solved: No attempts yet

Problem

Eunseong failed Day 2 of the 2024 International Olympiad in Informatics. Unwilling to admit his own shortcomings, he convinced himself that he had played badly because of a poor strategy. He wanted to plan better for future contests, so he considered the best strategy in the case where he knows in advance how long each problem takes to solve. But no one can know solving times before a contest, so he had not improved since the olympiad. One night he dreamed that he was taking Day 2 of the 2024 International Olympiad in Informatics again. In the dream, he knew exactly how long each subtask takes to solve. So he decided to find a way to maximize his score, even in the dream.

The contest has 3 problems and a time limit of $T$ seconds. The problems are numbered 1, 2, and 3. Each problem has $N$ subtasks, numbered 1 to $N$ . Eunseong knows that for each $1 \leq i \leq 3$ and $1 \leq j \leq N$ , subtask $j$ of problem $i$ is worth $P_{i,j}$ points and takes $t_{i,j}$ seconds to solve. Some subtasks deduct points when solved, so $P_{i,j}$ can be negative.

During the $T$ seconds of the contest, Eunseong may solve a particular subtask or do nothing. Subtasks form a strict order: to solve subtask $j$ of a problem, where $2 \leq j \leq N$ , he must have already solved subtask $j-1$ of that same problem. The final score is the sum of the points of all solved subtasks. Find the maximum score Eunseong can get in the contest.

Input

The first line contains $N$ and $T$ , separated by a space.

The next three lines give the subtask points. For each $1 \leq i \leq 3$ , line $1+i$ contains $P_{i,1}, P_{i,2}, \cdots, P_{i,N}$ , separated by spaces.

The next three lines give the solving times. For each $1 \leq i \leq 3$ , line $4+i$ contains $t_{i,1}, t_{i,2}, \cdots, t_{i,N}$ , separated by spaces.

Output

Print the maximum score Eunseong can get as a single integer.

Constraints

$1 \leq N \leq 10\ 000$
$1 \leq T \leq 10^9$
For each $1 \leq i \leq 3$ and $1 \leq j \leq N$ , $-30\ 000 \leq P_{i,j} \leq 30\ 000$ .
For each $1 \leq i \leq 3$ and $1 \leq j \leq N$ , $1 \leq t_{i,j} \leq 30\ 000$ .
All given numbers are integers.

Examples2

Example 1

Input

5 300
1 2 3 4 5
-10 -20 -30 -40 200
10 -2 -3 4 1
10 10 10 20 20
50 50 50 50 30
30 10 10 10 10

Expected output

Example 2

Input

Expected output