В ма­га­зи­не для упа­ков­ки по­дар­ков есть N ку­би­че­ских ко­ро­бок из ма­те­ри­а­лов двух видов. Самой ин­те­рес­ной счи­та­ет­ся упа­ков­ка по­дар­ка по прин­ци­пу матрёшки  — по­да­рок упа­ко­вы­ва­ет­ся в одну из ко­ро­бок, та, в свою оче­редь, в дру­гую ко­роб­ку и т. д. Все ко­роб­ки, ко­то­рые будут ис­поль­зо­ва­ны для упа­ков­ки по­дар­ка, ну­ме­ру­ют­ся с еди­ни­цы, на­чи­ная с той ко­роб­ки, в ко­то­рой будет на­хо­дить­ся по­да­рок. Одну ко­роб­ку можно по­ме­стить в дру­гую, если они из­го­тов­ле­ны из раз­ных ма­те­ри­а­лов, а длина её сто­ро­ны хотя бы на K + 2000 еди­ниц мень­ше длины сто­ро­ны дру­гой ко­роб­ки, где K  — по­ряд­ко­вый номер по­ме­ща­е­мой ко­роб­ки. Из­вест­ны длины сто­рон и ма­те­ри­ал ко­ро­бок, име­ю­щих­ся в на­ли­чии. Опре­де­ли­те наи­боль­шее ко­ли­че­ство ко­ро­бок, ко­то­рое можно ис­поль­зо­вать для упа­ков­ки од­но­го по­дар­ка и ми­ни­маль­но воз­мож­ную длину сто­ро­ны самой боль­шой из этих ко­ро­бок. Раз­мер по­дар­ка поз­во­ля­ет по­ме­стить его в самую ма­лень­кую ко­роб­ку.

Вход­ные дан­ные

В пер­вой стро­ке вход­но­го файла на­хо­дит­ся одно число N (N ≤ 1 000 000)  — ко­ли­че­ство ко­ро­бок. Каж­дая из сле­ду­ю­щих N строк со­дер­жит два раз­делённых про­бе­лом на­ту­раль­ных числа, каж­дое из ко­то­рых не пре­вы­ша­ет 1 000 000: длину сто­ро­ны и услов­ное обо­зна­че­ние вида ма­те­ри­а­ла ко­роб­ки (0 или 1).

За­пи­ши­те в от­ве­те два числа: сна­ча­ла наи­боль­шее ко­ли­че­ство ко­ро­бок, под­хо­дя­щих для упа­ков­ки по­дар­ка «матрёшкой», затем ми­ни­маль­но воз­мож­ную длину сто­ро­ны самой боль­шой ко­роб­ки.

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных во вход­ном файле

6

43 1

41 0

39 0

38 1

26 0

24 1

При­мер вход­но­го файла при­ведён для шести ко­ро­бок.

Ти­по­вой при­мер имеет ил­лю­стра­тив­ный ха­рак­тер. Для вы­пол­не­ния за­да­ния ис­поль­зуй­те дан­ные из при­ла­га­е­мых фай­лов.

Ответ:

В ма­га­зи­не для упа­ков­ки по­дар­ков есть N ку­би­че­ских ко­ро­бок из ма­те­ри­а­лов двух видов. Самой ин­те­рес­ной счи­та­ет­ся упа­ков­ка по­дар­ка по прин­ци­пу матрёшки  — по­да­рок упа­ко­вы­ва­ет­ся в одну из ко­ро­бок, та, в свою оче­редь, в дру­гую ко­роб­ку и т. д. Все ко­роб­ки, ко­то­рые будут ис­поль­зо­ва­ны для упа­ков­ки по­дар­ка, ну­ме­ру­ют­ся с еди­ни­цы, на­чи­ная с той ко­роб­ки, в ко­то­рой будет на­хо­дить­ся по­да­рок. Одну ко­роб­ку можно по­ме­стить в дру­гую, если они из­го­тов­ле­ны из раз­ных ма­те­ри­а­лов, а длина её сто­ро­ны хотя бы на K + 3000 еди­ниц мень­ше длины сто­ро­ны дру­гой ко­роб­ки, где K  — по­ряд­ко­вый номер по­ме­ща­е­мой ко­роб­ки. Из­вест­ны длины сто­рон и ма­те­ри­ал ко­ро­бок, име­ю­щих­ся в на­ли­чии. Опре­де­ли­те наи­боль­шее ко­ли­че­ство ко­ро­бок, ко­то­рое можно ис­поль­зо­вать для упа­ков­ки од­но­го по­дар­ка и ми­ни­маль­но воз­мож­ную длину сто­ро­ны самой боль­шой из этих ко­ро­бок. Раз­мер по­дар­ка поз­во­ля­ет по­ме­стить его в самую ма­лень­кую ко­роб­ку.

Вход­ные дан­ные

В пер­вой стро­ке вход­но­го файла на­хо­дит­ся одно число N (N ≤ 1 000 000)  — ко­ли­че­ство ко­ро­бок. Каж­дая из сле­ду­ю­щих N строк со­дер­жит два раз­делённых про­бе­лом на­ту­раль­ных числа, каж­дое из ко­то­рых не пре­вы­ша­ет 1 000 000: длину сто­ро­ны и услов­ное обо­зна­че­ние вида ма­те­ри­а­ла ко­роб­ки (0 или 1).

За­пи­ши­те в от­ве­те два числа: сна­ча­ла наи­боль­шее ко­ли­че­ство ко­ро­бок, под­хо­дя­щих для упа­ков­ки по­дар­ка «матрёшкой», затем ми­ни­маль­но воз­мож­ную длину сто­ро­ны самой боль­шой ко­роб­ки.

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных во вход­ном файле

6

43 1

41 0

39 0

38 1

26 0

24 1

При­мер вход­но­го файла при­ведён для шести ко­ро­бок.

Ти­по­вой при­мер имеет ил­лю­стра­тив­ный ха­рак­тер. Для вы­пол­не­ния за­да­ния ис­поль­зуй­те дан­ные из при­ла­га­е­мых фай­лов.

Ответ: