시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB402225.000%

문제

The inhabitants of Byteland have recently begun to travel more often than ever before. Enterprising ByteMan has had an idea of opening a travel agency. In the first day n customers came to the agency (we label them with integers ranging from 1 to n) and each of them would like to go to a trip. Unfortunately, every customer has his requirements.

Your task is to help ByteMan in choosing the customers who should go to the trip so that ByteMan's profit is maximized.

Each customer told ByteMan what value has the trip for him/her. Let xi be the value of the trip for the i-th customer (-1 000 000 ≤ xi ≤ 1 000 000). If xi ≥ 0, then this customer pays xi debillars for the trip, and if xi < 0, then ByteMan has to pay the i-th customer -xi debillars if this customer goes to the trip.

Apart from financial requirements, customers also have social requirements. The i-th customer has ki (0 ≤ kin - 1) such requirements; the j-th requirement of the i-th customer is represented by a pair of integers (aij, bij), (1 ≤ aijn, aij ≠ i, 1 ≤ bij ≤ 1 000 000). This requirement means that if the i-th customer goes to the trip, then the aij-th customer also has to go to the trip or the cost of the trip for the i-th customer has to be lowered by bij debillars (it might happen in such way that for some customers the cost of the trip will decrease from positive to negative and ByteMan will have to pay some debillars to such customers, so they will go to the trip not having some of their social requirements satisfied).

Help ByteMan in choosing the customers who should go to the trip so that ByteMan's profit is maximized (the number of customers who can be taken to the trip is not bounded).

입력

In the first line there is exactly one integer n (1 ≤ n ≤ 1 000), denoting the number of customers of the travel agency. The next n lines describe the customers. In the i + 1-th line (1 ≤ in) there are integers xi (-1 000 000 ≤ xi ≤ 1 000 000) and ki (0 ≤ kin - 1), and after them ki pairs of integers (aij, bij) (1 ≤ aijn, aij ≠ i, 1 ≤ bij ≤ 1 000 000) - all numbers in the line are separated by single spaces. You may assume that every customer has at most one social requirement concerning any other customer.

출력

In the first line of any output file there should be exactly one integer k (0 ≤ kn) - the number of customers, who should be taken to the trip by ByteMan. If the number k is positive, then the second line should contain k integers, separated by single spaces and denoting the numbers of customers who should be taken to the trip. If there are many optimal solutions, the output file should contain one of them. The numbers of customers can be given in any order.

예제 입력 1

4
5 0
6 2 1 10 3 1
-10 0
1 2 1 10 2 10

예제 출력 1

3
1 2 4