대회 전략

시간 제한2초메모리 제한1024 MB

요약

세 문제의 부분 과제마다 점수와 풀이 시간이 주어질 때, 각 문제에서 앞에서부터 순서대로 푸는 조건으로 전체 시간 T 안에서 얻을 수 있는 최대 점수를 구합니다.

난이도: 어려움10점 중 10점
유형: 동적 계획법, 분할 정복, 누적 합
정답자: 아직 제출이 없습니다

문제

2024년도 국제정보올림피아드 Day 2를 망친 은성이는 자신의 부족한 실력을 인정하기 싫어서, 대회에서 문제를 푸는 전략을 잘못 세운 탓에 실력을 발휘하지 못했다고 믿었다. 앞으로의 대회를 잘 준비하려고, 은성이는 각 문제를 푸는 데 걸리는 시간을 미리 알고 있을 때의 최적 전략을 고민했다. 하지만 대회 전에는 문제를 푸는 시간을 알 방법이 없어서, 은성이는 올림피아드 이후 실력이 늘지 않았다. 어느 날 은성이는 2024년도 국제정보올림피아드 Day 2를 다시 치르는 꿈을 꾸었다. 꿈 속의 은성이는 각 문제의 서브태스크를 해결하는 데 걸리는 시간을 정확히 알고 있었다. 은성이는 꿈에서라도 대회를 잘 치르기 위해 점수를 최대화하는 방법을 찾기로 했다.

대회에는 총 3문제가 출제되었고, 제한 시간은 $T$ 초이다. 3개의 문제에는 각각 1, 2, 3번이 붙어 있고, 각 문제는 1번부터 $N$ 번까지 번호가 붙은 $N$ 개의 서브태스크를 가진다. 은성이는 각 $1 \leq i \leq 3$ 과 $1 \leq j \leq N$ 에 대하여, $i$ 번 문제의 $j$ 번 서브태스크의 배점이 $P_{i,j}$ 이고 그 서브태스크를 해결하는 데 $t_{i,j}$ 초가 걸린다는 것을 알고 있다. 일부 서브태스크는 해결하면 점수가 감점된다. 즉 $P_{i,j}$ 는 음수일 수 있다.

은성이는 주어진 $T$ 초 동안 특정 서브태스크를 풀거나 아무것도 하지 않을 수 있다. 서브태스크는 순서가 분명해서, 어느 문제의 $j$ 번 서브태스크( $2 \leq j \leq N$ )를 해결하려면 같은 문제의 $j-1$ 번 서브태스크를 이미 해결한 상태여야 한다. 대회의 최종 점수는 해결한 모든 서브태스크 배점의 합이다. 은성이가 대회에서 얻을 수 있는 최대 점수를 구하라.

입력

첫째 줄에 $N$ 과 $T$ 가 공백으로 구분되어 주어진다.

이어서 세 줄에 걸쳐 각 문제의 서브태스크 배점이 주어진다. 각 $1 \leq i \leq 3$ 에 대하여, $1+i$ 번째 줄에는 $P_{i,1}, P_{i,2}, \cdots, P_{i,N}$ 이 공백으로 구분되어 주어진다.

이어서 세 줄에 걸쳐 각 문제의 서브태스크를 푸는 데 걸리는 시간이 주어진다. 각 $1 \leq i \leq 3$ 에 대하여, $4+i$ 번째 줄에는 $t_{i,1}, t_{i,2}, \cdots, t_{i,N}$ 이 공백으로 구분되어 주어진다.

출력

은성이가 얻을 수 있는 최대 점수를 정수 하나로 출력한다.

제한

$1 \leq N \leq 10\ 000$
$1 \leq T \leq 10^9$
각 $1 \leq i \leq 3$ 과 $1 \leq j \leq N$ 에 대하여, $-30\ 000 \leq P_{i,j} \leq 30\ 000$
각 $1 \leq i \leq 3$ 과 $1 \leq j \leq N$ 에 대하여, $1 \leq t_{i,j} \leq 30\ 000$
주어지는 모든 수는 정수이다.

예제2

예제 1

입력

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

예상 출력

예제 2

입력

예상 출력