ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC 2012, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Titan Ruins: Deadly Accuracy

Time limit: 1.0 second
Memory limit: 64 MB
`It worked! The door is open!' Soren said with relief. `We only have to do something with this huge pile of coins. It blocks the way.'
`Let's not waste time and blow them up. All these coins are really starting to annoy me,' Alba replied.
`Well, it's quite dangerous. Don't forget that the coins are magic, so when you cast a spell to destroy them, each coin strikes back with a shockwave of the same power as the spell. If we destroy k coins, the response will be k times stronger than our spell. We can kill ourselves just by casting a spell that is too powerful. The only good thing is that the shockwave energy has a bit different nature and will not cause new explosions.'
`Seems like we'll have to choose the power of each spell very carefully.'
`It's not that difficult. Each coin has its resistance limit. The Annihilation Spell destroys all the coins whose resistance limit is no greater than the power of the spell. We'll just have to cast the spell several times, each time increasing the power, that's all.'
`And how many times do we have to hide from the shockwaves?'
`It doesn't really matter. We only need to remove as many coins as we can without killing ourselves.'
`Yeah, but we better try to cast as few spells as possible.'


The first line contains two integers: n is the number of coins and p is the maximum shockwave power the wizards can survive (1 ≤ n ≤ 1000; 1 ≤ p ≤ 109). The second line contains n integers ai, which are the resistance limits of the coins (1 ≤ ai ≤ 106).


Output two integers separated with a space: the maximum amount of coins the wizards can destroy without killing themselves and the minimum number of spells they have to cast the Annihilation Spell to destroy all these coins.


5 4
4 1 4 1 2
3 2
Problem Author: Denis Dublennykh
Problem Source: NEERC 2012, Eastern subregional contest
To submit the solution for this problem go to the Problem set: 1917. Titan Ruins: Deadly Accuracy