문제
작년에 우리는 당신에게 비싼 금속을 납으로 바꾸는 일을 도와 달라고 부탁했다. (이전 문제에 대해 아무것도 알 필요는 없다.) 하지만 당신 나라의 지도자는 여전히 더 많은 납을 탐내고 있다!
세상에는 알려진 금속이 M가지 있으며, 당신 나라의 주기율표에서 납은 1번 금속이다. 지도자는 국고에 있는 금속들을 이용해 가능한 한 많은 납을 만들라고 당신에게 지시했다.
납을 포함한 각 금속 i에 대해, 그 금속 1그램을 파괴하고 두 금속을 각각 1그램씩 만들어내는 공식(변환식) 하나를 정확히 알고 있다. (질량 보존 법칙은 너무 깊게 생각하지 않는 편이 좋다!) i번째 금속의 공식이 결과물 중 하나로 i번째 금속을 만들어낼 수도 있다는 점에 유의하라. 이 공식들은 부분 그램(분수 그램)으로는 작동하지 않는다. 하지만 필요한 재료 금속을 1그램 가지고 있기만 하면, 각 공식을 원하는 만큼(또는 전혀) 사용할 수 있다.
최적으로 선택했을 때, 최종적으로 얻을 수 있는 납의 그램 수의 최댓값은 얼마인가? 아니면 그 값은 무한대(상한 없음)인가? 무한대가 아니라면 답이 매우 커질 수 있으므로, 결과를 소수 109+7(즉 1000000007)로 나눈 나머지만 출력하라.
입력
입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 정수 M으로 시작하며, 이는 세상에 알려진 금속의 개수이다. 그 다음 M줄이 이어지고, 각 줄에는 두 정수 Ri1, Ri2가 주어진다. (1부터 시작해) i번째 줄은 금속 i를 1그램 파괴하여 금속 Ri1 1그램과 금속 Ri2 1그램을 만들 수 있음을 뜻한다. 마지막으로 M개의 정수 G1, G2, ..., GM가 주어진 한 줄이 있다. Gi는 국고에 있는 금속 i의 그램 수이다. 납은 1번 금속이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라.
여기서 x는 (1부터 시작하는) 테스트 케이스 번호이다.
만들 수 있는 납의 최대량에 상한이 없다면 y는 UNBOUNDED여야 한다.
그렇지 않다면 y는 최종적으로 얻을 수 있는 납의 최대량(그램 단위)을
소수 109+7(즉 1000000007)로 나눈 나머지여야 한다.
예제
3
2
1 2
1 2
1 0
2
1 2
1 2
0 0
4
2 4
3 4
2 4
2 3
10 10 10 10
Case #1: UNBOUNDED
Case #2: 0
Case #3: 10
로그인해야 코드를 작성할 수 있어요.