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.

Input

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$$$;

Output

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

Note

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.

New Year's Gifts

Examples