401611: GYM100499 J Healthy Recipes

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Healthy Recipestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 Ai 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.

Input

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 Ai. (0 ≤ Ai ≤ 10000)
Output

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

ExamplesInput
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
Output
ENOUGH
10
Note

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

加入题单

上一题 下一题 算法标签: