A16775 | $New Year's Gifts$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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$ 个硬币的情况下，最多能让多少个朋友高兴。

输入 #1

输出 #1

2
0
2

C++ 编辑器

输入

输出