当前没有测试数据。

题目描述

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\cdot 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\cdot 10^5$；
• 所有测试用例的 $m$ 之和不超过 $2\cdot 10^5$。

输出格式

对每组测试用例，输出一个整数——Monocarp 最多能让多少位朋友开心。

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

说明

在第一个样例中，Monocarp 可以让两位朋友都开心：给第一位朋友一份价值 $3$ 金币的礼物，给第二位朋友一份价值 $2$ 金币的礼物并放进美观度为 $1$ 的盒子里。

在第二个样例中，Monocarp 无法让任何一位朋友开心：他没有足够的钱给任意一位朋友买价值达到 $z_i$ 的礼物；同时所有盒子的美观度都小于任意一位朋友对应的 $x_i$。

在第三个样例中，Monocarp 可以让两位朋友（第 $2$ 位和第 $3$ 位朋友）开心：给第一位朋友一份价值 $2$ 金币的礼物，给第二位朋友一份价值 $6$ 金币的礼物，给第三位朋友一份价值 $3$ 金币的礼物。

原题链接

原题链接