문제
목재상 정인이는 요즘 신이났다. 봄을 맞아 새롭게 집단장을 하려는 사람들로 주문이 밀려들고 있기 때문이다. 정인이가 취급하는 목재는 한 종류뿐이며 주문받은 길이만큼 잘라 판매한다. 예를 들어 정인이가 길이 8인 목재를 가지 있는 경우 주문에 따라 2와 6으로 잘라 2개의 목재로 팔 수도 있고, 길이 2짜리 4개로 잘라 팔 수도 있다. 정인이가 목재를 자를 때는 매직레이저를 이용하여 자르므로 톱밥이 생기지 않는다. 따라서 목재를 자를때 생기는 오차는 생각하지 않아도 된다. 수익보다 신용을 중요하게 생각하는 정인이는 가능한 많은 주문들에 목재를 공급하고자 한다. 정인이가 가지고 있는 목재의 개수와 각 목재의 길이, 그리고 주문의 개수와 각 주문의 길이를 입력받아 정인이가 공급할 수 있는 최대 주문수를 출력하는 프로그램을 작성하시오. 목재의 길이들은 서로 같은 목재가 존재할 수 있다.
입력
첫 행에 정인이가 가지고 있는 목재의 개수 N (1 ≤ N ≤ 50)이 입력된다. 이후 N행에 걸쳐 각 목재의 길이 Li (1 ≤ Li ≤ 10000) 가 입력된다. 다음 행에 주문의 개수 M(1 ≤ M ≤ 1023)이 입력된다. 이어서 M행에 걸쳐 주문받은 목재의 길이 Ki ( 1 ≤ Ki ≤ 128) 이 입력된다.
출력
정인이가 처리할 수 있는 가능한 많은 주문의 개수를 출력하시오. 정인이는 모든 주문을 처리하지 못할 수도 있다.
예제
3
50
60
15
5
45
25
15
25
35
4
출처
USACO
로그인해야 코드를 작성할 수 있어요.