C. Свобода выбора
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим анти-красоту мультимножества $$$\{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$$$ вы должны совершить следующее действие ровно один раз:

  1. Выбрать некое $$$v_i$$$ такое, что $$$l_i \le v_i \le r_i$$$
  2. Выбрать $$$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$$$, которой вы можете добиться.

Пример
Входные данные
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
Примечание

В первом наборе входных данных мультимножества имеют следующий вид:

  1. $$$\{10, 10, 10, 11, 11, 11, 12\}$$$. Из этого мультимножества нужно выбрать от $$$5$$$ до $$$6$$$ чисел.
  2. $$$\{12, 12, 12, 12\}$$$. Из этого мультимножества нужно выбрать от $$$1$$$ до $$$3$$$ чисел.
  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$$$, добиться не получится.