Дед Мороз и Сне­гу­роч­ка при­хо­дят на дет­ские утрен­ни­ки с меш­ком кон­фет. Дед Мороз делит кон­фе­ты по­ров­ну между всеми при­сут­ству­ю­щи­ми детьми (детей на утрен­ни­ке ни­ко­гда не бы­ва­ет боль­ше 100), а остав­ши­е­ся кон­фе­ты от­да­ет Сне­гу­роч­ке. Сне­гу­роч­ка каж­дый раз за­пи­сы­ва­ет в блок­нот ко­ли­че­ство по­лу­чен­ных кон­фет. Если кон­фе­ты раз­де­ли­лись между всеми детьми без остат­ка, Сне­гу­роч­ка ни­че­го не по­лу­ча­ет и ни­че­го не за­пи­сы­ва­ет. Когда утрен­ни­ки за­кон­чи­лись, Деду Мо­ро­зу стало ин­те­рес­но, какое число чаще всего за­пи­сы­ва­ла Сне­гу­роч­ка. Дед Мороз и Сне­гу­роч­ка  — вол­шеб­ные, по­это­му число утрен­ни­ков N, на ко­то­рых они по­бы­ва­ли, может быть очень боль­шим. На­пи­ши­те про­грам­му, ко­то­рая будет ре­шать эту за­да­чу. Перед тек­стом про­грам­мы крат­ко опи­ши­те ал­го­ритм ре­ше­ния за­да­чи и ука­жи­те ис­поль­зу­е­мый язык про­грам­ми­ро­ва­ния и его вер­сию.

Вам пред­ла­га­ет­ся два за­да­ния с по­хо­жи­ми усло­ви­я­ми: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. За­да­ние Б более слож­ное, его ре­ше­ние оце­ни­ва­ет­ся выше. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б.

За­да­ние А. Име­ет­ся набор чисел, со­сто­я­щий из 10 пар по­ло­жи­тель­ных целых чисел. В этом ва­ри­ан­те за­да­ния оце­ни­ва­ет­ся толь­ко пра­виль­ность про­грам­мы, время ра­бо­ты и раз­мер ис­поль­зо­ван­ной па­мя­ти не имеют зна­че­ния.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му – 2 балла.

За­да­ние Б. Име­ет­ся набор дан­ных, со­сто­я­щий из пар по­ло­жи­тель­ных целых чисел. По­ста­рай­тесь сде­лать про­грам­му эф­фек­тив­ной по вре­ме­ни и ис­поль­зу­е­мой па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству пар чисел N, т. е. при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз.

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если раз­мер па­мя­ти, ис­поль­зо­ван­ной в про­грам­ме для хра­не­ния дан­ных, не за­ви­сит от числа N и не пре­вы­ша­ет 1 ки­ло­бай­та.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и па­мя­ти,  — 4 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти,  — 3 балла.

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

В пер­вой стро­ке вво­дит­ся одно целое по­ло­жи­тель­ное число  — ко­ли­че­ство утрен­ни­ков N. Каж­дая из сле­ду­ю­щих N строк со­дер­жит два целых числа: сна­ча­ла D  — ко­ли­че­ство при­шед­ших на оче­ред­ной утрен­ник детей, а затем K – ко­ли­че­ство кон­фет в мешке Деда Мо­ро­за на этом утрен­ни­ке. Га­ран­ти­ру­ет­ся вы­пол­не­ние сле­ду­ю­щих со­от­но­ше­ний:

1 ≤ N ≤ 10000

1 ≤ D ≤ 100 (для каж­до­го D)

D ≤ K ≤ 1000 (для каж­дой пары D, K)

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

Про­грам­ма долж­на вы­ве­сти одно число  — то, ко­то­рое Сне­гу­роч­ка за­пи­сы­ва­ла чаще всего. Если не­сколь­ко чисел за­пи­сы­ва­лись оди­на­ко­во часто, надо вы­ве­сти боль­шее из них. Если Сне­гу­роч­ка ни разу ни­че­го не за­пи­сы­ва­ла, надо вы­ве­сти ноль.

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

7

10 58

15 315

20 408

100 1000

32 63

32 63

11 121

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

31

Дед Мороз и Сне­гу­роч­ка при­хо­дят на дет­ские утрен­ни­ки с меш­ком кон­фет. Дед Мороз делит кон­фе­ты по­ров­ну между всеми при­сут­ству­ю­щи­ми детьми (детей на утрен­ни­ке ни­ко­гда не бы­ва­ет боль­ше 100), а остав­ши­е­ся кон­фе­ты от­да­ет Сне­гу­роч­ке. Сне­гу­роч­ка каж­дый раз за­пи­сы­ва­ет в блок­нот ко­ли­че­ство по­лу­чен­ных кон­фет. Если кон­фе­ты раз­де­ли­лись между всеми детьми без остат­ка, Сне­гу­роч­ка ни­че­го не по­лу­ча­ет и ни­че­го не за­пи­сы­ва­ет. Когда утрен­ни­ки за­кон­чи­лись, Деду Мо­ро­зу стало ин­те­рес­но, сколь­ко раз­лич­ных чисел встре­ча­ет­ся в за­пи­сях Сне­гу­роч­ки. Дед Мороз и Сне­гу­роч­ка  — вол­шеб­ные, по­это­му число утрен­ни­ков N, на ко­то­рых они по­бы­ва­ли, может быть очень боль­шим. На­пи­ши­те про­грам­му, ко­то­рая будет ре­шать эту за­да­чу. Перед тек­стом про­грам­мы крат­ко опи­ши­те ал­го­ритм ре­ше­ния за­да­чи и ука­жи­те ис­поль­зу­е­мый язык про­грам­ми­ро­ва­ния и его вер­сию.

Же­ла­тель­но, чтобы про­грам­ма была эф­фек­тив­ной как по вре­ме­ни ра­бо­ты, так и по ис­поль­зу­е­мой па­мя­ти. Про­грам­му будем счи­тать эф­фек­тив­ной по па­мя­ти, если ис­поль­зу­е­мая па­мять не за­ви­сит от раз­ме­ра вход­ных дан­ных (то есть числа утрен­ни­ков). Про­грам­му будем счи­тать эф­фек­тив­ной по вре­ме­ни, если при уве­ли­че­нии раз­ме­ра вход­ных дан­ных N в t раз (t  — любое число) время её ра­бо­ты уве­ли­чи­ва­ет­ся не более чем в t раз.

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

В пер­вой стро­ке вво­дит­ся одно целое по­ло­жи­тель­ное число  — ко­ли­че­ство утрен­ни­ков N. Каж­дая из сле­ду­ю­щих N строк со­дер­жит два целых числа: сна­ча­ла D  — ко­ли­че­ство при­шед­ших на оче­ред­ной утрен­ник детей, а затем K – ко­ли­че­ство кон­фет в мешке Деда Мо­ро­за на этом утрен­ни­ке. Га­ран­ти­ру­ет­ся вы­пол­не­ние сле­ду­ю­щих со­от­но­ше­ний:

1 ≤ N ≤ 10000

1 ≤ D ≤ 100 (для каж­до­го D)

D ≤ K ≤ 1000 (для каж­дой пары D, K)

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

Про­грам­ма долж­на вы­ве­сти одно число  — ко­ли­че­ство раз­лич­ных чисел в за­пи­сях Сне­гу­роч­ки. Если Сне­гу­роч­ка ни разу ни­че­го не за­пи­сы­ва­ла, надо вы­ве­сти ноль.

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

7

10 58

15 315

20 408

100 1000

32 63

32 63

11 121

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

2