책 읽기
시간 제한40초메모리 제한1024 MB
각 독자가 읽는 페이지 수는 R의 배수이면서 찢긴 M개 페이지에 속하지 않는 번호의 개수이며, 모든 독자의 합을 구한다.
문제
Supervin은 1번부터 N번까지 번호가 붙은 N쪽짜리 고서를 관리하는 사서다. 책이 너무 오래되어 안타깝게도 M쪽이 찢겨 나갔다. 찢긴 쪽 번호는 P1, P2, ..., PM이다.
오늘 이 고서를 읽고 싶어 하는 게으른 독자가 Q명 있다. 이들은 게으르기 때문에 모든 쪽을 다 읽지는 않는다. i번째 독자는 번호가 Ri의 배수이면서 찢기지 않은 쪽만 읽는다. Supervin은 독자들이 읽은 쪽수의 합을 알고 싶어 한다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 따른다. 각 테스트 케이스의 첫 줄에는 책의 쪽수 N, 찢긴 쪽의 수 M, 독자의 수 Q가 주어진다. 둘째 줄에는 M개의 정수가 주어지며, i번째 정수는 Pi이다. 셋째 줄에는 Q개의 정수가 주어지며, i번째 정수는 Ri이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 모든 독자가 읽게 될 쪽수의 합이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ P1 < P2 < ... < PM ≤ N.
- 모든 i에 대해 1 ≤ Ri ≤ N.
힌트
예제 1에서 첫 번째 독자는 2, 4, 6, 10번 쪽을 읽는다. 8번 쪽은 찢겨 나갔으므로 읽지 않는다. 두 번째 독자는 3, 6, 9번 쪽을 읽는다. 따라서 모든 독자가 읽는 쪽수의 합은 4 + 3 = 7이다.
예제 2에서는 모든 쪽이 찢겨 나갔으므로 모든 독자는 0쪽을 읽는다.
예제 3에서 첫 번째 독자는 주어진 여섯 쪽을 제외한 모든 쪽을 읽는다.