페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5921

졸업 준비 2s 2048MB

문제

코딩만 열심히 한 서준이는 졸업을 앞두게 되었다.

코딩만 열심히 한 서준이는 다른 과목들을 듣지 않아 결국 졸업에 실패할 위기에 놓였다.

코딩만 열심히 한 서준이는 안타깝게도 선 지식이 하나도 없다.

갑자기 어려운 과목을 들을 수 없기에, 다른 과목을 들어서 지식 수준을 쌓은 후 어려운 과목을 들어야 한다.

과목은 n개가 있으며 지식은 k개의 종류가 있다.

i번 과목을 듣기 위해서는 i번 과목이 요구하는 k개의 지식 수준을 전부 만족해야 한다.

i번 과목을 들었다면, i번 과목이 주는 k개의 지식 수준을 얻게 된다.

코딩만 열심히 한 서준이는 코딩으로 이 위기를 넘기고자 한다.

코딩만 열심히 한 서준이를 도와 최대 몇 과목을 들을 수 있는지 계산하자.

[제약 조건]

1 \le n,\ k \le 10^6

n \cdot k \le 10^6

0 \le u[i][j],\ r[i][j] \le 10^9 (모든 1 \le i \le n 과 1 \le j \le k 에 대해)


입력

첫 줄에 n, k가 주어진다.

그 다음 n줄에 걸쳐 1 \sim i 번 과목을 듣기 위한 k개의 지식의 수준 주어진다.

그 다음 n줄에 걸쳐 1 \sim i 번 과목을 들을 시 얻게 되는 k개의 지식 수준이 주어진다.


출력

들을 수 있는 최대 과목 수를 출력한다.


부분문제

번호 점수 조건
#112점

n=1

#228점

1 \le n,k \le 100

#321점

k=1

#439점

추가 제약 조건 없음.


예제 #1

3 3
0 0 0
7 9 2
7 8 9
7 8 2
7 7 7
8 10 9
1

처음에는 [0, 0, 0]의 지식을 필요로 하는 1번 과목만 들을 수 있다. 이 과목을 들으면 서준이는 3종류의 지식에 대해 7,8,2 지식 수준을 얻게 된다. 하지만 이 이후로는 다른 과목을 듣기에 지식 수준이 부족하여 들을 수 없다. 따라서 답은 1 과목이다.


예제 #2

4 3
5 1 0
0 1 5
0 0 0
7 7 7
0 5 6
1 1 1
8 2 0
8 1 4
4

3번, 1번, 2번, 4번 과목 순서대로 들으면 총 4개의 과목을 들을 수 있다.

처음에 지식 수준은 [0,0,0] 이며, 3번 과목은 [0,0,0] 지식 수준을 요구하기에 들을 수 있다. 따라서 [8,2,0] 만큼의 지식을 얻게 된다.

다음에 지식 수준은 [8,2,0] 이며, 1번 과목은 [5,1,0] 지식 수준을 요구하기에 들을 수 있다. 따라서 [0,5,6] 만큼의 지식을 얻게 된다.

다음에 지식 수준은 [8,7,6] 이며, 2번 과목은 [0,1,5] 지식 수준을 요구하기에 들을 수 있다. 따라서 [1,1,1] 만큼의 지식을 얻게 된다.

다음에 지식 수준은 [9,8,7] 이며, 4번 과목은 [7,7,7] 지식 수준을 요구하기에 들을 수 있다. 따라서 [8,1,4] 만큼의 지식을 얻게 된다.


예제 #3

5 5
14 11 15 7 15
0 0 0 0 0
9 9 14 2 13
4 3 6 1 0
2 4 7 0 0
5 5 0 0 13
4 4 7 1 0
4 1 0 2 1
2 5 0 2 1
4 0 7 2 12
4


출처

NOI 2023 1번
로그인해야 코드를 작성할 수 있어요.