AE1B - Tables


Byteman works as a carpenter. He has just received an order for s pine-wood tables. Although he has plenty of pine-wood boards in his workshop, he has just run out of screws. Therefore he needs to walk to the warehouse and bring back some boxes with screws. What is the minimum number of boxes that he needs to bring in order to have enough screws to make the tables?

Input

The first line of the standard input contains three integers n, k, and s (1 ≤ n, k, s ≤ 1000) separated with single spaces. They denote the number of boxes with screws in Byteman's warehouse, the number of screws needed to make a table and the number of tables to be made by Byteman, respectively. The second line contains n (not necessarily different) integers ai (1 ≤ ai ≤ 1000) separated with single spaces, such that ai is the number of screws in the ith box in the warehouse.

Output

The first and only line of the standard output should contain a single integer - the minimal number of boxes with screws that Byteman needs to bring from his warehouse in order to make s tables. You may assume that Byteman has enough screws in the warehouse to make all tables.

Example

For the input data:

5 6 3
3 9 5 7 3

the correct result is:

3

Explanation of the example. To make three tables, each of which requires six screws, Byteman has to bring three boxes with screws from the warehouse. These can be either the ones containing 3, 7 and 9 screws, or the ones with 9, 5 and 7 screws.

Task author: Jakub Lacki.


hide comments
:D: 2012-06-21 10:45:07

Moved to tutorial. Easy and pretty almost exactly the same as STAMPS, like others said.

albertg: 2012-06-21 08:39:51

Should be moved to tutorials!

:): 2012-06-21 02:25:59

which sorting method should be used???
i use bubble and getting many TLE.it is slow

noju: 2012-04-23 05:41:27

bubble sort may not work out ..i got too many WA coz of this.!!

Mukul: 2012-04-09 08:15:30

Just copy paste the solution of STAMPS...:P:P

Buda IM (retired): 2011-04-17 14:53:20

Same problem as STAMPS.

Bharath Sivaram: 2011-01-13 12:04:57

Any tricky cases??? am getting WA but my program is perfect

Mohammed Hafez: 2010-09-22 07:07:07

Thanks alot.

Alex: 2010-09-21 05:37:58

There are some tricky things regarding equal numbers. Don't rush.

Mohammed Hafez: 2010-09-15 07:54:17

Still need to know.
Just any invalid test case.


Added by:Race with time
Date:2009-05-03
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Algorithmic Engagements 2009