E. Новогодние подарки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа $$$n$$$ друзей, и он решил подарить каждому из них новогодний подарок. Он также подготовил $$$m$$$ коробок для размещения подарков; красота $$$i$$$-й коробки $$$a_i$$$. В каждую коробку можно положить не более одного подарка.

Монокарп хочет подарить подарок стоимостью не менее $$$y_i$$$ монет $$$i$$$-му другу. Кроме того, он знает, что $$$i$$$-й друг будет счастлив, если выполнено хотя бы одно из следующих условий:

  • подарок находится в коробке с красотой не менее $$$x_i$$$;
  • подарок стоит не менее $$$z_i$$$ ($$$z_i \gt y_i$$$).

Ваша задача — помочь Монокарпу вычислить максимальное количество друзей, которых он может сделать счастливыми, если у него есть $$$k$$$ монет. Обратите внимание, что Монокарп должен купить подарок для каждого друга, и подарок необязательно должен быть в коробке.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^{15}$$$).

Вторая строка содержит $$$m$$$ целых чисел $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le m$$$).

Затем следуют $$$n$$$ строк; $$$i$$$-я из них содержит три целых числа $$$x_i$$$, $$$y_i$$$ и $$$z_i$$$ ($$$1 \le x_i \le m$$$; $$$1 \le y_i \lt z_i \le 10^9$$$).

Дополнительные ограничения на входные данные:

  • $$$\sum\limits_{i=1}^{n} y_i \le k$$$.
  • сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$;
  • сумма $$$m$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$;
Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество друзей, которых Монокарп может сделать счастливыми, если у него есть $$$k$$$ монет.

Пример
Входные данные
3
2 1 6
1
1 2 3
1 2 7
2 2 3
1 1
2 1 3
2 1 5
3 4 11
1 2 2 1
3 2 5
4 4 6
3 1 3
Выходные данные
2
0
2
Примечание

В первом примере Монокарп может сделать обоих друзей счастливыми следующим образом: подарить первому другу подарок за $$$3$$$ монеты, а второму другу подарок за $$$2$$$ монеты в коробке с красотой $$$1$$$.

Во втором примере Монокарп не может сделать счастливыми ни одного из своих друзей, потому что у него недостаточно денег, чтобы купить подарок за $$$z_i$$$ монет даже для одного из них; также все коробки имеют меньше красоты, чем любое из $$$x_i$$$.

В третьем примере Монокарп может сделать счастливыми двух друзей ($$$2$$$-го и $$$3$$$-го) следующим образом: подарить первому другу подарок за $$$2$$$ монеты, второму другу подарок за $$$6$$$ монет, и третьему другу подарок за $$$3$$$ монеты.