Со­рев­но­ва­ния по игре «Тет­рис-он­лайн» про­во­дят­ся по сле­ду­ю­щим пра­ви­лам:

1.  Каж­дый участ­ник ре­ги­стри­ру­ет­ся на сайте игры под опре­делённым иг­ро­вым име­нем. Имена участ­ни­ков не по­вто­ря­ют­ся.

2.  Чем­пи­о­нат про­во­дит­ся в те­че­ние опре­делённого вре­ме­ни. В любой мо­мент этого вре­ме­ни любой за­ре­ги­стри­ро­ван­ный участ­ник может зайти на сайт чем­пи­о­на­та и на­чать зачётную игру. По окон­ча­нии игры её ре­зуль­тат (ко­ли­че­ство на­бран­ных очков) фик­си­ру­ет­ся и за­но­сит­ся в про­то­кол.

3.  Участ­ни­ки имеют право иг­рать не­сколь­ко раз. Ко­ли­че­ство по­пы­ток од­но­го участ­ни­ка не огра­ни­чи­ва­ет­ся.

4.  Окон­ча­тель­ный ре­зуль­тат участ­ни­ка опре­де­ля­ет­ся по одной, луч­шей для дан­но­го участ­ни­ка игре.

5.  Более вы­со­кое место в со­рев­но­ва­ни­ях за­ни­ма­ет участ­ник, по­ка­зав­ший луч­ший ре­зуль­тат.

6.  При ра­вен­стве ре­зуль­та­тов более вы­со­кое место за­ни­ма­ет участ­ник, рань­ше по­ка­зав­ший луч­ший ре­зуль­тат.

В ходе со­рев­но­ва­ний за­пол­ня­ет­ся про­то­кол, каж­дая стро­ка ко­то­ро­го опи­сы­ва­ет одну игру и со­дер­жит ре­зуль­тат участ­ни­ка и его иг­ро­вое имя. Про­то­кол фор­ми­ру­ет­ся в ре­аль­ном вре­ме­ни по ходу про­ве­де­ния чем­пи­о­на­та, по­это­му стро­ки в нём рас­по­ло­же­ны в по­ряд­ке про­ве­де­ния игр: чем рань­ше встре­ча­ет­ся стро­ка в про­то­ко­ле, тем рань­ше за­кон­чи­лась со­от­вет­ству­ю­щая этой стро­ке игра.

Спон­сор чем­пи­о­на­та предо­ста­вил призы раз­лич­ной цен­но­сти для на­граж­де­ния К луч­ших иг­ро­ков (К<=20). Если участ­ни­ков ока­жет­ся мень­ше К, при­за­ми на­граж­да­ют­ся все. Вам не­об­хо­ди­мо на­пи­сать эф­фек­тив­ную, в том числе по па­мя­ти, про­грам­му, ко­то­рая по дан­ным про­то­ко­ла опре­де­ля­ет К луч­ших иг­ро­ков и за­ня­тые ими места. 

Перед тек­стом про­грам­мы крат­ко опи­ши­те ал­го­ритм ре­ше­ния за­да­чи и ука­жи­те ис­поль­зу­е­мый язык про­грам­ми­ро­ва­ния и его вер­сию.

Опи­са­ние вход­ных дан­ных

Пер­вая стро­ка со­дер­жит числа К  — ко­ли­че­ство име­ю­щих­ся при­зов и N  — общее ко­ли­че­ство строк про­то­ко­ла.

Каж­дая из сле­ду­ю­щих N строк со­дер­жит за­пи­сан­ные через про­бел ре­зуль­тат участ­ни­ка (целое по­ло­жи­тель­ное число, не пре­вы­ша­ю­щее 100 мил­ли­о­нов) и иг­ро­вое имя (имя не может со­дер­жать про­бе­лов). Стро­ки ис­ход­ных дан­ных со­от­вет­ству­ют стро­кам про­то­ко­ла и рас­по­ло­же­ны в том же по­ряд­ке, что и в про­то­ко­ле.

Опи­са­ние вы­ход­ных дан­ных

Про­грам­ма долж­на вы­ве­сти имена и ре­зуль­та­ты К луч­ших иг­ро­ков в по­ряд­ке за­ня­тых мест по форме, при­ведённой ниже в при­ме­ре. Если иг­ро­ков ока­жет­ся мень­ше К, нужно вы­ве­сти дан­ные обо всех иг­ро­ках.

При­мер вход­ных дан­ных:

6 15

69485 Jack

95715 qwerty

95715 Alex

83647 M

197128 qwerty

95715 Jack

93289 Alex

95715 Alex

95715 M

32768 BilboBaggins

99824 TetrisMaster

45482 BilboBaggins

62123 BilboBaggins

77623 M

56791 Champion

При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных:

1.  qwerty (197128)

2.  TetrisMaster (99824)

3.  Alex (95715)

4.  Jack (95715)

5.  M (95715)

6.  BilboBaggins (62123)