루미 알고리즘

#1602플래티넘Bartering

PO 2025 결선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
112N = 3
210k_i = 1
325There 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.
426K ≤ 1000
527No 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

출처 표기

출처: Programmeringsolympiaden 2025년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.