We’re preparing your current view and syncing the latest data.
You have n items and n sellers. Each seller sells some subset of items with corresponding prices. Your goal is to buy each item from some seller offering it at the minimum price possible. Determine the minimum number of sellers you need to purchase from to ensure all items are bought at their lowest possible price.
The first line contains an integer n (number of items and sellers). Then n lines follow; each line describes a seller. The i-th line starts with the integer k_i (number of items sold by i-th seller), followed by k_i pairs of integers (item_j, price_j), describing the item index and the price offered by that seller for that item.
Print a single integer — the minimum number of sellers needed to buy all items at minimum prices.
1 <= n <= 10^3 1 <= item_j <= n 1 <= price_j <= 10^9
Example 1
Input
3 2 1 1 2 1 2 2 1 3 1 1 3 1
Output
2
Explanation
Items 1, 2, and 3 have minimum prices of 1. Seller 1 sells items 1 and 2 at price 1, seller 2 sells items 2 and 3 at price 1, and seller 3 sells item 3 at price 1. To cover all items at minimum price, buying from sellers 1 and 2 suffices.