В мор­ском порту го­то­вят­ся к пе­ре­воз­ке гру­зов раз­ной массы и формы, для этого каж­дый груз по­ме­ща­ют в от­дель­ный кон­тей­нер. Кон­тей­не­ры имеют раз­ную гру­зо­подъ­ем­ность (не­ко­то­рые кон­тей­не­ры могут иметь оди­на­ко­вую гру­зо­подъёмность). Из-за ком­пью­тер­но­го сбоя из об­ще­го ко­ли­че­ства кон­тей­не­ров для пе­ре­воз­ки вы­де­ли­ли пер­вые по­пав­ши­е­ся кон­тей­не­ры. На­пи­ши­те про­грам­му, ко­то­рая по­мо­жет по­счи­тать мак­си­маль­ное ко­ли­че­ство гру­зов, ко­то­рое можно от­пра­вить в вы­де­лен­ных кон­тей­не­рах, и мак­си­маль­ную массу од­но­го от­прав­лен­но­го груза.

Фор­мат вход­ных дан­ных:

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

Фор­мат вы­ход­ных дан­ных:

Два целых не­от­ри­ца­тель­ных числа: мак­си­маль­ное ко­ли­че­ство гру­зов, ко­то­рое можно от­пра­вить в вы­де­лен­ных кон­тей­не­рах и мак­си­маль­ную массу од­но­го от­прав­лен­но­го груза.

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

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

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

Два целых не­от­ри­ца­тель­ных числа: мак­си­маль­ное число гру­зов и мак­си­маль­ную массу груза.

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

7

10 50

20 60

70 20

40 20

50 10

10 10

20 15

Для при­ведённого при­ме­ра от­ве­том яв­ля­ет­ся пара чисел: 6; 50.

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

Ответ:

В мор­ском порту го­то­вят­ся к пе­ре­воз­ке гру­зов раз­ной массы и формы, для этого каж­дый груз по­ме­ща­ют в от­дель­ный кон­тей­нер. Кон­тей­не­ры имеют раз­ную гру­зо­подъ­ем­ность (не­ко­то­рые кон­тей­не­ры могут иметь оди­на­ко­вую гру­зо­подъёмность). Из-⁠за ком­пью­тер­но­го сбоя из об­ще­го ко­ли­че­ства кон­тей­не­ров для пе­ре­воз­ки вы­де­ли­ли пер­вые по­пав­ши­е­ся кон­тей­не­ры. На­пи­ши­те про­грам­му, ко­то­рая по­мо­жет по­счи­тать мак­си­маль­ное ко­ли­че­ство гру­зов, ко­то­рое можно от­пра­вить в вы­де­лен­ных кон­тей­не­рах, и мак­си­маль­ную массу од­но­го от­прав­лен­но­го груза.

Фор­мат вход­ных дан­ных.

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

Фор­мат вы­ход­ных дан­ных.

Два целых не­от­ри­ца­тель­ных числа: мак­си­маль­ное ко­ли­че­ство гру­зов, ко­то­рое можно от­пра­вить в вы­де­лен­ных кон­тей­не­рах и мак­си­маль­ную массу од­но­го от­прав­лен­но­го груза.

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

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

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

Два целых не­от­ри­ца­тель­ных числа: мак­си­маль­ное число гру­зов и мак­си­маль­ную массу груза.

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

7

10 50

20 60

70 20

40 20

50 10

10 10

20 15

Для при­ведённого при­ме­ра от­ве­том яв­ля­ет­ся пара чисел: 6; 50.

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

Ответ: