1239 - I am a PR man:: HUST Online Judge

1239 - I am a PR man

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 338

Solved: 78

Description

I work in a big corporation
My occupation is to handle public relations
Everyday I tangle with newspaper and TV stations
Just to keep my company in smooth public situations

Today my boss had me in his office
Told me that we’ve got a serious complexion to deal with
A journalist wrote that on rivals we are doing nasty things
And I must put an end to defamations like this

The boss said:
"Limited budget you’ve got
Contact many newspaper editors you must
Different effect will come out
It only depends on which with editor you choose to dine out

Of course this isn’t a pleasant affair
So I don’t want everybody to be aware
To a certain degree make it clear
And what you do in detail – I don’t care

As always I am an entrepreneur
I don’t want nobody to say I’m a coward
I’m generous is what I want to hear
So spent the money I gave you – entire!"

Everybody say my boss is wacky
And he is always tough on me
What a difficult task he set me
Even Ethan Hunt won’t be glad to take it!

I asked,
"What if I fail to finish this task?"
Boss said
"Stupid question you just asked,
No one ever dare to disappoint me in the past
So get going and move your ass!"

With so many listed editors to go to
With a certain degree of effect I must reach to
With a certain amount of money for me to work though
Please somebody tell me what am I supposed to do!

Input

The first line contain a integer T(1<=T<=10) indicate the number of test cases include.
For each case, in the first line there will be 3 integers, N(1<=N<=50), M(1<=M<=500), K(1<=K<=500), indicating how many editors are on the list, the amount of money must be spent up, and the degree of effect must reach (Both money and effect must be EXACT the amount input).
In the following N lines there will be 2 integers in each line, indicating the cost of the editor and the effect can get from this editor.(both are nonnegative numbers)

Output

One line for each case. Only a single integer, indicates how many plan there will be to meet the demand.

sample input

sample output

hint

source

<a href="http://www.gaewah.com/">Gaewah</a>