피자 판매

고객이 두 종류의 피자 A와 B를 파는 피자가게에서 피자를 주문하려 한다. 각 피자는 여러 개의 조각으로 미리 나누어져 있으며, 조각에 적힌 숫자는 그 조각의 크기를 나타낸다.

<그림 1>

손님이 원하는 전체 크기를 말하면, 피자가게는 한 종류의 피자에서 두 조각 이상을 팔 때 반드시 서로 이웃한 연속된 조각들을 잘라서 판다. 판매하는 조각들은 모두 A 피자에서만 고를 수도 있고, 모두 B 피자에서만 고를 수도 있으며, A와 B를 함께 사용할 수도 있다. 판매한 조각들의 크기 합은 손님이 주문한 크기와 정확히 같아야 한다.

예를 들어 <그림 1>과 같은 피자가 있을 때 손님이 전체 크기 7의 피자를 주문하면, 피자가게는 <그림 2>와 같이 5가지 방법으로 피자를 판매할 수 있다.

<그림 2>

손님이 원하는 크기의 피자를 판매하는 모든 방법의 수를 계산하는 프로그램을 작성하시오.

첫 번째 줄에 손님이 구매하려는 피자 크기 K가 주어진다. K는 2,000,000 이하의 자연수이다.

두 번째 줄에는 A 피자와 B 피자의 조각 개수 m, n이 순서대로 주어진다. 3 <= m, n <= 1000이다.

이어서 m개의 줄에는 A 피자의 조각 크기가 시계 방향 순서로 주어진다. 그 다음 n개의 줄에는 B 피자의 조각 크기가 시계 방향 순서로 주어진다. 각 조각의 크기는 1000 이하의 자연수이다.

첫 번째 줄에 피자를 판매할 수 있는 방법의 수를 출력한다. 방법이 없으면 0을 출력한다.