URI Online Judge | 2726

Full Sleigh

By Francisco Elio Parente Arcos Filho, UEA BR Brazil

Timelimit: 1

It's Christmas Eve, and it's almost time for the sled to leave. Everything is already in Santa's sack and the reindeer in position, there is only one thing left: decide which helpers will work with Noel this year. Yes, contrary to popular belief, the good old man does not do everything himself. He always takes with him a group of elves on his round the world in one night.

However, the elves must be chosen carefully, because their weight will directly affect the aerodynamics of the Sled. If it is very light it will swing very much during the flight and if it is very heavy it will tire the reindeers very early.

As it is in hurry Noel decided to make a try and chose a group of helpers. But the Reindeers soon accused them of being too light. Then Noel made a second attempt, chose another group. But again the Reindeers complained, however, stating that it was now too heavy. The good old man, who has an appointment time, became irritated and gave an ultimatum to his subordinates: "That's enough! Choose K elves soon to go in such a way that the sled is neither too light nor too heavy! That is, the sum of the weights can not be less than that of the first group that I tried and neither greater than the second one.

Of course the little ones despaired. Apart from the restriction of weights and now the number of Elves that have to be exact, they still have the fact that each Elf weighs twice as much or more than an Elf younger than him. Which obviously only complicates everything.

Knowing that all Elves are of different ages can you help these little ones tell how many ways they can choose a group to go with Santa respecting all the requirements?


The first line of the entry contains an integer T that represents the number of test cases. Then there are T test cases. The first line of a test case contains two integers N (1 ≤ N ≤ 50) and K (1 ≤ K ≤ 50) respectively representing the total number of Elves and the determined number of Elves to be boarded on the sled. The second line of a test case contains N integers Pi (1 ≤ Pi ≤ 1018) representing the weight in mg of the Elves. The third and last line of a test case contains two integers A and B (0 ≤ AB ≤ 1019) representing respectively the weight of the lighter group tested and the weight of the heaviest group tested. Both in mg.


The output is composed of one line per test case containing an integer representing the number of ways to choose a group according to requirements.

Input Sample Output Sample

3 2
10 1 3
4 13
4 3
20 10 50 1
21 81
6 3
14 70 3 1 6 31
10 74