Определим анти-красоту мультимножества \(\{b_1, b_2, \ldots, b_{len}\}\) как количество вхождений числа \(len\) в это мультимножество.
Вам дано \(m\) мультимножеств, \(i\)-е мультимножество содержит \(n_i\) различных элементов, а конкретно: \(c_{i, 1}\) копий числа \(a_{i,1}\), \(c_{i, 2}\) копий числа \(a_{i,2}, \ldots, c_{i, n_i}\) копий числа \(a_{i, n_i}\). Гарантируется, что \(a_{i, 1} < a_{i, 2} < \ldots < a_{i, n_i}\). Также вам даны числа \(l_1, l_2, \ldots, l_m\) и \(r_1, r_2, \ldots, r_m\) такие, что \(1 \le l_i \le r_i \le c_{i, 1} + \ldots + c_{i, n_i}\).
Создадим мультимножество \(X\), изначально пустое. Далее, для всех \(i\) от \(1\) до \(m\) вы должны совершить следующее действие ровно один раз:
- Выбрать некое \(v_i\) такое, что \(l_i \le v_i \le r_i\)
- Выбрать \(v_i\) любых чисел из \(i\)-го мультимножества и добавить их в мультимножество \(X\).
Ваша задача выбрать \(v_1, \ldots, v_m\) и добавленные числа так, чтобы в итоге мультимножество \(X\) имело минимально возможную анти-красоту.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(m\) (\(1 \le m \le 10^5\)) — количество мультимножеств.
Далее для каждого \(i\) от \(1\) до \(m\) следует блок данных из трёх строк.
Первая строка каждого блока содержит целые числа \(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}\)) — количество различных чисел в \(i\)-м мультимножестве и границы на количество чисел, которое надо добавить из \(i\)-го мультимножества в \(X\).
Вторая строка каждого блока содержит \(n_i\) целых чисел \(a_{i, 1}, \ldots, a_{i, n_i}\) (\(1 \le a_{i, 1} < \ldots < a_{i, n_i} \le 10^{17}\)) — различные элементы \(i\)-го мультимножества.
Третья строка каждого блока содержит \(n_i\) целых чисел \(c_{i, 1}, \ldots, c_{i, n_i}\) (\(1 \le c_{i, j} \le 10^{12}\)) — количества копий элементов в \(i\)-м мультимножестве.
Гарантируется, что сумма значений \(m\) по всем наборам входных данных не превосходит \(10^5\), а также сумма \(n_i\) по всем блокам всех наборов входных данных не превосходит \(10^5\).
Выходные данные
Для каждого набора входных данных выведите минимально возможную анти-красоту мультимножества \(X\), которой вы можете добиться.
Примечание
В первом наборе входных данных мультимножества имеют следующий вид:
- \(\{10, 10, 10, 11, 11, 11, 12\}\). Из этого мультимножества нужно выбрать от \(5\) до \(6\) чисел.
- \(\{12, 12, 12, 12\}\). Из этого мультимножества нужно выбрать от \(1\) до \(3\) чисел.
- \(\{12, 13, 13, 13, 13, 13\}\). Из этого мультимножества нужно выбрать \(4\) числа.
Можно выбрать из первого мультимножества элементы \(\{10, 11, 11, 11, 12\}\), из второго: \(\{12\}\), из третьего: \(\{13, 13, 13, 13\}\). Итого \(X = \{10, 11, 11, 11, 12, 12, 13, 13, 13, 13\}\). Размер \(X\) равен \(10\), число \(10\) входит в \(X\) ровно \(1\) раз, а значит анти-красота \(X\) равна \(1\). Можно показать, что анти-красоты меньшей чем \(1\), добиться не получится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3
3 5 6
10 11 12
3 3 1
1 1 3
12
4
2 4 4
12 13
1 5
1
7 1000 1006
1000 1001 1002 1003 1004 1005 1006
147 145 143 143 143 143 142
1
2 48 50
48 50
25 25
2
1 1 1
1
1
1 1 1
2
1
1
1 1 1
1
2
2
1 1 1
1
1
2 1 1
1 2
1 1
2
4 8 10
11 12 13 14
3 3 3 3
2 3 4
11 12
2 2
|
1
139
0
1
1
0
0
|