33637번 - 6교시: 국어 (Hard)

문제

이 문제는 4교시: 국어 (Easy)와 입력 및 시간 제한만 다른 상위 문제입니다.

치스는 국어 수업 시간에 밀린 다른 과목 숙제를 하려고 합니다. 하지만 선생님은 수업에 집중하지 않는 것을 싫어하시기 때문에, 수업 시간에 숙제하는 것을 들키지 않도록 조심해야 합니다.

선생님은 수업 중 특정 시각에 학생들을 바라보는데, 이 순간에 치스가 문제를 풀기 시작하거나 푸는 중이면 들킵니다. 단, 정확히 선생님이 바라보는 순간 문제를 끝까지 풀었다면 들키지 않습니다. 수업은 0ドル$초에 시작하며, 동시에 선생님이 학생들을 바라봅니다. 또한, 수업이 끝날 때도 선생님은 학생들을 바라봅니다.

치스는 과학, 수학, 영어 숙제를 해야 합니다. 각 숙제는 여러 문제로 구성되며, 치스는 다음 규칙에 따라 숙제하려고 합니다.

• 한 번 풀기 시작한 문제는 반드시 끝까지 풀어야 합니다. 문제를 풀다 말고 다른 문제를 풀기 시작할 수 없습니다. 또한, 풀고 있던 문제를 끝까지 풀었다면 시간 소모 없이 그 즉시 다른 문제를 풀기 시작할 수 있습니다.
• 한 과목의 숙제를 모두 끝마치지 않았더라도 풀고 있던 문제를 끝까지 풀었다면 다른 과목 숙제의 문제를 풀 수 있습니다.
• 각 과목의 숙제를 할 때에는, 해당하는 과목의 숙제 문제 중 문제 번호가 가장 작은 문제부터 풀어야 합니다.

예를 들어, 수학의 2ドル$번 문제를 먼저 풀고 나서 수학의 1ドル$번 문제를 풀 수 없습니다. 그러나 수학의 1ドル$번 문제를 풀고 난 다음 영어의 1ドル$번 문제를 푸는 것은 가능합니다.

선생님이 학생들을 바라보는 시각과 각 숙제 문제를 푸는 데 걸리는 시간이 주어졌을 때, 치스가 수업 시간 안에 최대 몇 개의 문제를 풀 수 있는지 구하세요.

입력

첫 번째 줄에 선생님이 학생들을 바라보는 횟수를 나타내는 정수 $N$이 주어집니다. $(2 \leq N \leq 1,000円)$

두 번째 줄에 국어 수업의 총시간을 나타내는 정수 $T$가 주어집니다. $(N-1 \leq T \leq 10^5)$

세 번째 줄에 공백을 간격으로 선생님이 학생들을 바라보는 특정한 시각을 나타내는 정수 $t_1,ドル $t_2,ドル $\cdots,ドル $t_N$이 오름차순으로 주어집니다. $(0 = t_1 \lt t_2 \lt \cdots \lt t_N=T)$

네 번째 줄에 과학 숙제의 문제 수 $S,ドル 수학 숙제의 문제 수 $M,ドル 영어 숙제의 문제 수 $E$가 공백을 간격으로 주어집니다. $(1 \leq S, M, E \leq {\color{red}{400}})$

다섯 번째 줄에 과학 숙제의 $i$번째 문제를 푸는 데에 걸리는 시간을 나타내는 $S$개의 정수 $a_1,ドル $a_2,ドル $\cdots,ドル $a_S$가 공백을 간격으로 주어집니다. $(1 \leq a_i \leq 1,000円)$

여섯 번째 줄에 수학 숙제의 $i$번째 문제를 푸는 데에 걸리는 시간을 나타내는 $M$개의 정수 $b_1,ドル $b_2,ドル $\cdots,ドル $b_M$이 공백을 간격으로 주어집니다. $(1 \leq b_i \leq 1,000円)$

일곱 번째 줄에 영어 숙제의 $i$번째 문제를 푸는 데에 걸리는 시간을 나타내는 $E$개의 정수 $c_1,ドル $c_2,ドル $\cdots,ドル $c_E$가 공백을 간격으로 주어집니다. $(1 \leq c_i \leq 1,000円)$

시간은 모두 초 단위를 사용합니다.

출력

첫 번째 줄에 치스가 수업 시간 안에 풀 수 있는 숙제 문제의 최대 개수를 출력해 주세요.

제한

힌트