401611: GYM100499 J Healthy Recipes

Over the last few months, Conan has trained very intensively for competing in the ACM/ICPC contest. What he did are just eating, sleeping and coding; as a result, he has put on quite a few kilos. Since the training period are about to finish, he is planning to come back to a healthier life style: going to the gym and eating more properly.

There are N delicious dishes, dish i has A_i calories. A recipe for a meal is the combination of dishes where each dish appears no more than 1. A perfect, healthy recipe should have the total calories of M calories.

Conan is planning his meals to details and he wonders will there be enough K different perfect recipes for the next K days. 2 recipes are considered different if there is at least a dish appears in one recipe but not the other.

The input starts with the number T (T ≤ 500)- the number of tests. Then T tests follow.

• The first line of each test is 3 integers N, M, K.(1 ≤ N ≤ 100, 0 ≤ M ≤ 10000, 1 ≤ K ≤ 100).
• The second line of each test consist of N integers A_i. (0 ≤ A_i ≤ 10000)

For each test, if there are at least K different perfect recipes, print “ENOUGH”; otherwise you should print the number of perfect recipes.

2
10 1000 7
100 200 300 400 500 600 700 800 900 1000
10 1000 30
100 200 300 400 500 600 700 800 900 1000

ENOUGH
10

All the dishes in 2 samples are similar. There are 10 different perfect recipes:

1000 = 100 + 200 + 300 + 400

1000 = 100 + 200 + 700

1000 = 100 + 300 + 600

1000 = 100 + 400 + 500

1000 = 100 + 900

1000 = 200 + 300 + 500

1000 = 200 + 800

1000 = 300 + 700

1000 = 400 + 600

1000 = 1000