Egy műsorban guglerek (a Gugli cég alkalmazottjai) táncolnak. A tácosokat hárotagú zsüri értékeli, minden táncos három egész pontszámot kap, 0 és 10 között. A zsüri tagjainak eléggé hasonló az ízlése, ezért meglepő, ha   egy táncos kapott két olyan pontszámot, amelyek különbsége 2. (Olyan soha nem történik, hogy 2-nél nagyobb lenne a különbség.)

Pédául  (8, 8, 8) és  (7, 8, 7) nem meglepő, (6, 7, 8) és (6, 8, 8) meglepő, (7, 6, 9) pedig nem fordulhat elő.

A gugler összpontszáma a három pontszám összege. A legjobb eredmény pedig a három pontszám maximuma. Az érdekel minket, hogy a guglerek összpontszámának ismeretében hány táncos legjobb eredménye lehet legalább p.

Például legyen hat táncos, a következő összpontokkal: 29, 20, 8, 18, 18, 21. Tudjuk, hogy két meglapő eredmény volt. Szeretnénk tudni, hogy hány gugler legjobb eredménye érte el a 8 pontot.

Lehettek volna például ezek a pontszámok:

(*) jelöli a meglepő eredményeket. Ekkor három gugler ért el 8 vagy több pontot. 

Írjunk programot, ami a guglerek összpontszámának és a meglepő pontszámok számának ismeretében megadja, hogy hány táncos legjobb eredménye lehet legalább p.

Az első sorban a tesztesetek T száma van, ezután T eset következik. Minden teszteset egyetlen - szóközökkel elválasztott - sorból áll, és egész számokat tartalmaz. Az első szám N, a guglerek száma, a második S a meglepő eredmények száma, a harmadik p, a megadott küszöbérték. Ezután N darab t_i egész következik, a guglerek összpontszáma. 

Minden tesztesetre írjuk ki, hogy legfeljebb hány guglernek lehet a legjobb eredménye nagyobb vagy egyenlő, mint p.

Bemenet	Kimenet
4 3 1 5 15 13 11 3 0 8 23 22 21 2 1 1 8 0 6 2 8 29 20 8 18 18 21	Case #1: 3 Case #2: 2 Case #3: 1 Case #4: 3

A feladat forrása: Google Code Jam 2012 Qualification Round

Algoritmusok: mohó algoritmus

megoldás