C. Freedom of Choice
brute force; greedy; implementation
Let's define the anti-beauty of a multiset \(\{b_1, b_2, \ldots, b_{len}\}\) as the number of occurrences of the number \(len\) in the multiset.You are given \(m\) multisets, where the \(i\)-th multiset contains \(n_i\) distinct elements, specifically: \(c_{i, 1}\) copies of the number \(a_{i,1}\), \(c_{i, 2}\) copies of the number \(a_{i,2}, \ldots, c_{i, n_i}\) copies of the number \(a_{i, n_i}\). It is guaranteed that \(a_{i, 1} < a_{i, 2} < \ldots < a_{i, n_i}\). You are also given numbers \(l_1, l_2, \ldots, l_m\) and \(r_1, r_2, \ldots, r_m\) such that \(1 \le l_i \le r_i \le c_{i, 1} + \ldots + c_{i, n_i}\).Let's create a multiset \(X\), initially empty. Then, for each \(i\) from \(1\) to \(m\), you must perform the following action exactly once: Choose some \(v_i\) such that \(l_i \le v_i \le r_i\) Choose any \(v_i\) numbers from the \(i\)-th multiset and add them to the multiset \(X\).You need to choose \(v_1, \ldots, v_m\) and the added numbers in such a way that the resulting multiset \(X\) has the minimum possible anti-beauty.
Each test consists of multiple test cases. The first line contains a single integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer \(m\) (\(1 \le m \le 10^5\)) — the number of given multisets.Then, for each \(i\) from \(1\) to \(m\), a data block consisting of three lines is entered.The first line of each block contains three integers \(n_i, l_i, r_i\) (\(1 \le n_i \le 10^5, 1 \le l_i \le r_i \le c_{i, 1} + \ldots + c_{i, n_i} \le 10^{17}\)) — the number of distinct numbers in the \(i\)-th multiset and the limits on the number of elements to be added to \(X\) from the \(i\)-th multiset.The second line of the block contains \(n_i\) integers \(a_{i, 1}, \ldots, a_{i, n_i}\) (\(1 \le a_{i, 1} < \ldots < a_{i, n_i} \le 10^{17}\)) — the distinct elements of the \(i\)-th multiset.The third line of the block contains \(n_i\) integers \(c_{i, 1}, \ldots, c_{i, n_i}\) (\(1 \le c_{i, j} \le 10^{12}\)) — the number of copies of the elements in the \(i\)-th multiset.It is guaranteed that the sum of the values of \(m\) for all test cases does not exceed \(10^5\), and also the sum of \(n_i\) for all blocks of all test cases does not exceed \(10^5\).
For each test case, output the minimum possible anti-beauty of the multiset \(X\) that you can achieve.
In the first test case, the multisets have the following form: \(\{10, 10, 10, 11, 11, 11, 12\}\). From this multiset, you need to select between \(5\) and \(6\) numbers. \(\{12, 12, 12, 12\}\). From this multiset, you need to select between \(1\) and \(3\) numbers. \(\{12, 13, 13, 13, 13, 13\}\). From this multiset, you need to select \(4\) numbers.You can select the elements \(\{10, 11, 11, 11, 12\}\) from the first multiset, \(\{12\}\) from the second multiset, and \(\{13, 13, 13, 13\}\) from the third multiset. Thus, \(X = \{10, 11, 11, 11, 12, 12, 13, 13, 13, 13\}\). The size of \(X\) is \(10\), the number \(10\) appears exactly \(1\) time in \(X\), so the anti-beauty of \(X\) is \(1\). It can be shown that it is not possible to achieve an anti-beauty less than \(1\).