시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 0 0 0 0.000%

문제

Banks lend money to each other. In tough economic times, if a bank goes bankrupt, it may not be able to pay back the loan. A bank’s total assets are its current balance plus its loans to other banks. The diagram in the figure below shows five banks. The banks’ current balances are 25, 125, 175, 75, and 181 million (RM) Ringgit Malaysia, respectively. The directed edge from node 1 to node 2 indicates that bank 1 lends 40 million RM to bank 2.

If a bank’s total assets are under a certain limit, the bank is unsafe. The money it borrowed cannot be returned to the lender, and the lender cannot count the loan in its total assets. Consequently, the lender may also be unsafe, if its total assets are under the limit. Write a program to find all the unsafe banks.

입력

The first line has a positive integer T, (1 <= T <= 100), denoting the number of test cases. The test cases are given in the following lines. Each test case start with a line that consist of two integers n (1 <= n <= 10), where n indicates the number of banks and limit, (100 <= limit <= 1000) is the minimum total assets for keeping a bank safe. Then there will be n lines that describe the information for n banks with IDs from 0 to n-1. The first number in the line is the bank’s balance, the second number indicates the number of banks that borrowed money from the bank, and the rest are pairs of two numbers. Each pair describes a borrower. The first number in the pair is the borrower’s ID and the second is the amount borrowed.

출력

For each test case produce a single line of output that start with prefix “Case # x:” where x represents the case number (starting from one) followed by the bank ID(s) which is unsafe.

예제 입력 1

2
5 201
25 2 1 100.5 4 320.5
125 2 2 40 3 85
175 2 0 125 3 75
75 1 0 125
181 1 2 125
5 300
30 2 2 90 1 160.4
80 1 0 100
190 1 2 90
300 2 0 136 3 90
65 1 0 96

예제 출력 1

Case # 1:3 1 
Case # 2:0 1 2 4