Time Limit: 3s
Memory Limit: 128MB
유빗드는 뜨개질을 하는 것을 좋아한다. 특히 직물로 된 천을 뜨개질 하는 것을 좋아하는데, 그가 가장 최근에 짠 직물은 4x4 크기의 격자무늬 천이다.
유빗드가 이번에 짜려고 하는 직물은 일정 패턴을 가진 세로로 매우 긴 천을 만드려고 한다. 이 작품의 이름을 "사복(絲服) - 중력전쟁"으로 짓고, 어떤 패턴으로 뜨개질을 시작할지도 정했다. 패턴을 만들기 위해선 n과 길이가 k인 배열 p[]가 필요하다.
우선 초기에 세로로 n줄만큼 베이스 실을 만들고, 그다음 이전에 사용한 실보다 p1를 더한 개수의 실을 사용해서 다른 색상의 실로 줄을 이어나갈 것이다. 그 다음에는 이전에 사용한 실의 개수에서 p2를 더한 수만큼의 실을 사용해 다음 줄을 이어나가고... 이런식으로 서로 다른 m개의 색상에 대해서 실을 이어나가려고 한다. 필요한 패턴 번호가 k보다 크다면, 그 번호에서 k의 배수를 빼 1과 k 사이의 값으로 만든 뒤 그 값에 해당하는 패턴 값을 사용한다. 만약 k+2번째 색상을 이용해서 뜨개질 줄을 이어나가려면, 이전 줄에서 p1을 더한 수만큼의 실을 사용해 줄을 이어나가고, k+3번째는 p2를 더한 수만큼의 실을 사용할 것이다.
예를 들어 n이 3이고 패턴으로 2가 정해졌다면, 처음에는 3개의 줄로 만들고, 그 다음 두번째 실로는 5줄을, 3번째 색상의 실로는 7줄을 만들어나갈 것이다. 만약 실 색상이 3가지가 전부라면, 이 직물을 짜는데 필요한 실은 15줄이 된다.
좀 더 복잡한 예를 들어보자. 만약 초기에 50줄을 짜고, 패턴으로는 +6, -2, -2, +0 을 사용한다면, 각 색상마다 사용되는 실은 50, 56, 54, 52, 52, 58, 56, 54, 54 ... 줄을 사용할 것이다. 만약 실의 색상이 6가지가 전부라면 직물을 짜는데 사용된 실은 322줄이다.
유빗드는 자신의 역작 사복 - 중력전쟁을 완성하는데 필요한 실의 줄수가 궁금하다. 사용 가능한 실의 색상의 가지수와 직물의 패턴 정보가 주어졌을 때, 필요한 실의 줄 수를 구하는 프로그램을 만들어보자.
입력으로는 여러 데스트케이스가 존재할 수 있다.
각 테스트케이스는 2개의 줄로 이루어져 있는데, 첫번째 줄에는 3개의 정수 N M K 가 들어온다. N은 처음에 베이스로 사용할 실의 줄수이며 (1 ≤ N ≤ 100) M은 실의 색상의 가지수 (1 ≤ M ≤ 1,000), K는 패턴의 길이이다. (1 ≤ K ≤ 100)
두번째 줄에는 K개의 정수가 들어온다. 각 수는 패턴에 사용되는 숫자들이며, 그 값의 절대값은 100이 넘지 않는다.
직물을 짜는 과정에서 필요한 실의 줄 수가 0보다 작거나 같아지는 경우가 없다고 가정해도 좋다.
입력의 마지막은 N M K값 대신 0 0 0이 들어온다.
각 테스트케이스마다 한줄에 하나씩 직물을 완성하는데 필요한 실의 줄 수를 출력한다.
3 3 1 2 50 6 4 6 -2 -2 0 0 0 0
15 322