Monocarp 有 $$$n$$$ 个朋友,决定给他们每人一份新年礼物。他还准备了$$$m$$$盒子来放置礼物;第 $$$i$$$ 个盒子的美丽在于 $$$a_i$$$。每个盒子最多可容纳一件礼物。
Monocarp 希望向第 $$$i$$$ 位好友送出一份至少价值 $$$y_i$$$ 硬币的礼物。此外,他知道第 $$$i$$$ 个朋友会很高兴,如果 至少一个 满足以下条件:
- 礼物装在一个盒子里,漂亮至少$$$x_i$$$;
- 礼物至少价值 $$$z_i$$$ ($$$z_i \gt 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$$$ 行;其中第 $$$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$$$;
输出
对于每个测试用例,打印一个整数——如果 Monocarp 拥有 $$$k$$$ 硬币,他可以高兴的最大可能数量的朋友。
示例
输入复制
32 1 611 2 31 2 72 2 31 12 1 32 1 53 4 111 2 2 13 2 54 4 63 1 3
输出复制
202
注意
在第一个例子中,Monocarp 可以让两个朋友都开心,如下:给第一个朋友一份价值 $$$3$$$ 硬币的礼物,给第二个朋友一份价值 $$$2$$$ 硬币的礼物,装在一个有 $$$1$$$ 美丽的盒子里。
在第二个例子中,Monocarp 无法让他的任何朋友开心,因为他没有足够的钱为其中一个朋友购买 $$$z_i$$$ 硬币的礼物;而且,所有的盒子都没有$$$x_i$$$那么漂亮。
在第三个例子中,Monocarp 可以让两个朋友($$$2$$$-nd 朋友和 $$$3$$$-rd 朋友)高兴如下:给第一个朋友一份 $$$2$$$ 硬币的礼物,给第二个朋友一份 $$$6$$$ 硬币的礼物,给第三个朋友一份 $$$3$$$ 硬币的礼物。