EQWE is a pastry chef who has  friends. This year (obviously, the year 2021), he wants to give each friend a birthday cake made by himself.

If EQWE wants to give the -th friend a birthday cake made by himself, he need  days (do NOT need to be contiguous) before his friend's birthday to make it. After that he will get  favorable impression. Note that it will be OK for him to finish the cake exactly on the birthday, as birthday parties are always held at night.

But EQWE doesn't have much time and he has another plan. There are  special gifts in the shop. EQWE can pay  yuan to get the -th special gift and send it to any friend. Note that each gift is unique, which means that he can buy each gift at most once. After that he will get  favorable impression.

EQWE's friends are very polite, so they do NOT want to receive more than one gift (including birthday cakes and special gifts). Note that to gain some favorable impression from a friend, the selected gift must be sent on the exact date of the friend's birthday.

Suppose that it is the first day of the year 2021 now (and he can start making birthday cakes immediately), and EQWE has  yuan. What's the maximum number of favorable impression that EQWE can get in 2021?

输入描述:

The input file starts with an integer , denoting the number of test cases. Then  test cases follow.

For each test case, the first line contains three integers , denoting the number of friends, the number of special gifts, and the amount of money that EQWE has.

Each of the following $N$ lines describes a friend, in the format of , where  is the date of the friend's birthday,  is the day needed to make the birthday cake for the friend, and  is the favorable impression that EQWE can get. It is guaranteed that  are integers. It is also guaranteed that the date given are all valid dates between the year 1990 and 2010, that is, $year$ is an integer between 1990 and 2010, $month$ is an integer between 1 and 12, and $day$ is a positive integer which do not exceed the number of days in the given month.

The next   lines describe the special gifts, the -th of which contain two inte The  line is 

输出描述:

For each test case, output a line containing a single integer, denoting the maximum number of favorable impression that EQWE can get.

1
2 2 100
2000-01-01 10 13
2000-12-31 30 92
99 46
2 2

138

备注:

It is commonly known that a year is divide into 12 months, and for the most of the time the numbers of days in each month are 31,28,31,30,31,30,31,31,30,31,30 and 31. The only exception is that for leap years the second month contains 29 days. Of the time range mentioned in the problem (that is, from 1990 to 2021), the leap years are 1992, 1996, 2000, 2004, 2008, 2012, 2016 and 2020.