CF2182E.New Year's Gifts

Monocarp has $n$ friends and decided to give a New Year's gift to each of them. He has also prepared $m$ boxes to place the gifts in; the beauty of the $i$-th box is $a_i$. Every box can contain at most one gift.

Monocarp wants to give a gift worth at least $y_i$ coins to the $i$-th friend. Additionally, he knows that the $i$-th friend will be happy if at least one of the following conditions holds:

• the gift is in a box with beauty at least $x_i$;
• the gift is worth at least $z_i$ ($z_i \gt y_i$).

Your task is to help Monocarp calculate the maximum possible number of friends he can make happy if he has $k$ coins. Note that Monocarp must purchase a gift for each friend, and the gift may not necessarily come in a box.

Monocarp 有 $n$ 位朋友，并决定给每位朋友赠送一份新年礼物。他还准备了 $m$ 个盒子来盛放这些礼物；第 $i$ 个盒子的美观度为 $a_i$。每个盒子最多只能装一份礼物。

Monocarp 希望送给第 $i$ 位朋友的礼物价值至少为 $y_i$ 枚金币。此外，他知道第 $i$ 位朋友会感到开心，当且仅当满足以下至少一个条件：

• 礼物被放在美观度至少为 $x_i$ 的盒子中；
• 礼物本身的价值至少为 $z_i$（其中 $z_i > y_i$）。

你的任务是帮助 Monocarp 计算：在总预算为 $k$ 枚金币的前提下，他最多能让多少位朋友感到开心？注意，Monocarp 必须为每位朋友都购买一份礼物，且该礼物不一定非得装入盒子中。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 2 \cdot 10^5$; $1 \le k \le 10^{15}$).

The second line contains $m$ integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le m$).

Then $n$ lines follow; the $i$-th of them contains three integers $x_i$, $y_i$ and $z_i$ ($1 \le x_i \le m$; $1 \le y_i \lt z_i \le 10^9$).

Additional constraints on the input:

• $\sum\limits_{i=1}^{n} y_i \le k$.
• the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$;
• the sum of $m$ over all test cases doesn't exceed $2 \cdot 10^5$;

第一行包含一个整数 $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$；

For each test case, print a single integer — the maximum possible number of friends Monocarp can make happy if he has $k$ coins.

对于每个测试用例，输出一个整数——即 Monocarp 拥有 $k$ 枚硬币时，最多能让多少位朋友开心。

In the first example, Monocarp can make both friends happy as follows: give the first friend a gift for $3$ coins, and give the second friend a gift for $2$ coins in a box with $1$ beauty.

In the second example, Monocarp cannot make any of his friends happy, because he does not have enough money to buy a gift for $z_i$ coins for even one of them; also, all the boxes have less beauty than any of the $x_i$.

In the third example, Monocarp can make two friends (the $2$-nd friend and the $3$-rd friend) happy as follows: give the first friend a gift for $2$ coins, and give the second friend a gift for $6$ coins, and give the third friend a gift for $3$ coins.

在第一个例子中，Monocarp 可以通过以下方式让两位朋友都开心：给第一位朋友赠送一个价值 $3$ 枚硬币的礼物，给第二位朋友赠送一个装在美观度为 $1$ 的礼盒中、价值 $2$ 枚硬币的礼物。

在第二个例子中，Monocarp 无法让任何一位朋友开心，因为他甚至没有足够的钱为其中任意一位朋友购买价值 $z_i$ 枚硬币的礼物；此外，所有礼盒的美观度均小于任意一个 $x_i$。

在第三个例子中，Monocarp 可以让两位朋友（即第 $2$ 位朋友和第 $3$ 位朋友）开心，方法如下：给第一位朋友赠送一个价值 $2$ 枚硬币的礼物，给第二位朋友赠送一个价值 $6$ 枚硬币的礼物，给第三位朋友赠送一个价值 $3$ 枚硬币的礼物。