CF2182E New Year's Gifts

Monocarp 有 $n$ 个朋友，他决定在新年时给每个朋友送一份礼物。他还准备了 $m$ 个盒子来放置礼物，第 $i$ 个盒子的美观度为 $a_i$。每个盒子最多只能装一个礼物。 Monocarp 想给第 $i$ 个朋友的礼物至少价值 $y_i$ 硬币。此外，他知道第 $i$ 个朋友在以下两个条件至少满足一个时会感到高兴： - 礼物放在美观度至少为 $x_i$ 的盒子里； - 礼物价值至少为 $z_i$（$z_i > y_i$）。 你的任务是帮助 Monocarp 计算在他有 $k$ 个硬币的情况下，他最多能让多少个朋友高兴。注意，Monocarp 必须给每个朋友买一件礼物，且礼物不一定需要放在盒子里。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n, m, k$（$1 \le n, m \le 2 \times 10^5$；$1 \le k \le 10^{15}$）。 第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$（$1 \le a_i \le m$）。 接下来的 $n$ 行，每行包含三个整数 $x_i, y_i, z_i$（$1 \le x_i \le m$；$1 \le y_i < z_i \le 10^9$）。 输入的额外约束： - $\sum\limits_{i=1}^{n} y_i \le k$。 - 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。 - 所有测试用例中 $m$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示在 Monocarp 拥有 $k$ 个硬币的情况下，最多能让多少个朋友高兴。

在第一个样例中，Monocarp 可以让两个朋友都高兴：给第一个朋友一个价值 $3$ 硬币的礼物，给第二个朋友一个价值 $2$ 硬币的礼物并放入美观度为 $1$ 的盒子中。 在第二个样例中，Monocarp 不能让任何朋友高兴，因为他没有足够的钱给任何一个朋友买价值 $z_i$ 的礼物，并且所有盒子的美观度都小于所有 $x_i$。 在第三个样例中，Monocarp 可以让两位朋友（第 $2$ 个和第 $3$ 个朋友）高兴：给第一个朋友一个价值 $2$ 硬币的礼物，给第二个朋友一个价值 $6$ 硬币的礼物，给第三个朋友一个价值 $3$ 硬币的礼物。 由 ChatGPT 5 翻译