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

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

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

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

과목은 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 에 대해)

졸업 준비 timer 2s memory 2048MB

졸업 준비 2s 2048MB