레이팅 미적용고객이 두 종류의 피자 \(A\)와 \(B\)를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다.
<그림 1>
고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 \(A\)종류이거나, 모두 \(B\)종류이거나, 또는 \(A\)와 \(B\) 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.
<그림 2>
피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로그램을 작성하시오
첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 \(A\), \(B\) 피자의 피자조각의 개수를 나타내 는 정수 \(m\), \(n\) 이 차례로 주어진다 \((3 \le m,\) \(n \le 1000).\) 세 번째 줄부터 차례로 \(m\) 개의 줄에는 피자 \(A\)의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 \(n\) 개의 줄에는 차례로 피자\(B\)의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.
첫째 줄에는 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.
7
5 3
2
2
1
7
2
6
8
3
5
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2001 > 2차 대회 > 중등부 3번