Shoe Shopping
Национална Олимпиада по Информатика 2012, Кръг 3
Time Limit: 0.2s, Memory Limit: 64MiB
Ели, както всяко момиче, е маниачка на тема обувки. Но като специалист в това отношение, тя знае, че има обувки и обувки. Най-скъпите са боклуци – цената им е висока единствено заради марката или като рекламен трик. Най-евтините също са боклуци – кофти качество. Затова, когато пазарува, Ели е решила да си взима най-скъпите обувки под определена цена, докато има пари, след което приключва с пазаруването (дори да има пари за други, по-евтини чифтове). Обърнете внимание на следващия пример, тъй като нейната стратегия не е много интуитивна.

Нека, например, по магазините има 7 чифта обувки, с цени, съответно, 70, 10, 130, 50, 40, 20, и 40 лева. Да кажем също така, че Ели има 150 лева, като е решила да си купува обувки не по-скъпи от 100 лева. Така тя ще разглежда само чифтовете с цени 70, 10, 50, 40, 20, и 40 лева. Най-скъпите от тях са тези с цена 70, и тъй като тя има бюджет за тях си ги взима, като й остават 80 лева. Следващите по цена са тези за 50 лева. Тя има пари и за тях, затова също ги взема, като й остават 30 лева. След тях идва (някой от двата) чифта за 40 лева, но тя вече няма пари да си ги вземе, затова приключва с пазаруването. Забележете, че тя не купува тези за 20 или 10 лева, въпреки, че има пари за тях, тъй като вече е стигнала до чифт, който не може да си купи (по нейната логика те ще са твърде некачествени). Така, по времето на тази шопинг терапия, тя ще си е взела 2 чифта.

В следствие на честите си посещения на моловете, Ели знае всички продавани обувки с техните цени. Тя се чуди колко пари да си вземе и какъв лимит на цената на най-скъпите обувки да си постави. Помогнете й, като напишете програма, която по дадена информация за обувките и две числа – парите, които има и максимална цена на обувките, връща колко чифта би си взела тя, спазвайки нейната стратегия на пазаруване.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и Q – съответно броя чифтове обувки, които има по магазините, и броя питания, които ще направи Ели към вашата програма. На втория ред ще има N цели числа P1, P2, …, PN – цената на всеки от чифтовете обувки. На всеки от следващите Q реда ще има по две цели числа Mi и Кi – съответно с колко пари разполага Ели и каква е цената на най-скъпите обувки, които тя би си взела, за съответния въпрос.
Изход
На стандартния изход изведете Q реда с по едно единствено цяло число – колко обувки би си купила Ели при дадените Mi и Ki.
Ограничения
  • 1 ≤ N, Q, Pi, Ki ≤ 100,000
  • 1 ≤ Mi ≤ 1,000,000
Примерен Вход Примерен Изход
7 5 70 10 130 50 40 20 40 150 100 140 50 190 130 60 80 300 60 2 3 1 0 5
При първото питане Ели би взела обувките с цени (70, 50). При второто - тези с цени (50, 40, 40). За третото само тези с цена 130. При четвъртото Ели не успява да си купи обувките за 70, затова спира без да си е купила нищо. В последния случай Ели би си купила всички обукви с цена по-малка или равна на 60 лева.
Мрън!