그림 전시회를 앞두고 전시할 작품을 고르려고 한다. 전시회에서는 각 작품을 액자에 넣어 일렬로 전시할 예정이다.

N개의 후보 작품이 1부터 N으로 번호가 붙어있다. 이때, i번째 작품의 크기는 S_i이고, 값어치는 V_i이다.

또한 M개의 액자들이 1부터 M으로 번호가 붙어있다. 이때, j번째 작품의 크기는 C_j이며, 각 액자에는 크기가 C_j 이하인 작품만이 들어갈 수 있으며, 오직 하나의 작품만이 들어갈 수 있다.

모든 그림은 액자에 넣어야만 전시가 가능한데, 아래와 같은 두 조건을 충족해야만 한다.

최대한 많은 그림을 전시하려고 한다면, 최대 몇 개의 그림까지 전시가 가능한지 알아보자.

전시회 준비 timer 1s memory 512MB

전시회 준비 1s 512MB