영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
We have all heard the fascinating story of how someone managed to trade a paperclip for a pen, then traded the pen for a door handle, and so on, until they eventually traded their way to a house. In today's housing market, you think this sounds like a brilliant idea and decide to try something similar.
After analyzing the market, you realize that there are N distinct items and M possible trades. A trade consists of a set of items that you can exchange for exactly one other item. For example, a trade could be 2 apples and 3 pears for an orange. Formally, a trade can be described as
C_{i,0} · F_0 + C_{i,1} · F_1 + … + C_{i,N-1} · F_{N-1} ⇒ 1 · F_{r_i}.
Here, C_{i,j} is the coefficient for F_j in trade i. This means that C_{i,j} is the number of F_j required for the trade. r_i is the item you receive as a result of trade i. Note that not all items need to be part of a particular trade; for these items, C_{i,j} = 0.
Each trade can be performed any number of times. Your goal is to calculate how many paperclips are needed to acquire a house.
The item F_0 represents the paperclip, and the item F_{N-1} represents the house.
Input
The first line contains two integers N and M (2 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5), the number of items and the number of trades.
Next, the M trades are described. Each description begins with two integers r_i (0 ≤ r_i < N) and k_i (1 ≤ k_i ≤ N), where r_i is the item you receive from trade i, and k_i is the number of distinct items used in the trade.
Then follow k_i lines, each containing two integers C_{i,j} (1 ≤ C_{i,j} ≤ 100) and j (0 ≤ j < N), which indicate that the coefficient C_{i,j} belongs to item F_j in the trade. Note that items with coefficient 0 are not included in the input.
Let K be the sum of all k_i values across all trades. It holds that K ≤ 10^5.
It is guaranteed that all items can be obtained by starting with a paperclip, and you can purchase each item for at most 10^9 paperclips each.
Output
Print a single integer: the minimum number of paperclips required to trade your way to a house.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 12 | N = 3 |
| 2 | 10 | k_i = 1 |
| 3 | 25 | There is an order of items such that for every item f, all trades where f is received only contain items that come earlier in the order than f. |
| 4 | 26 | K ≤ 1000 |
| 5 | 27 | No additional constraints. |
예제
예제 1
4 4 1 1 5 1 2 1 2 0 1 2 2 0 1 2 3 2 1 1 1 2
6
예제 2
3 2 1 1 7 0 2 1 8 1
56