Дано N де­та­лей, номер де­та­ли сов­па­да­ет со стро­кой, и счи­та­ет­ся от 1 до N, в N стро­ках со­от­вет­ствен­но: время шли­фов­ки, время по­крас­ки. Есть кон­вей­ер­ная лента длины N, тре­бу­ет­ся от­шли­фо­вать и по­кра­сить де­та­ли, их ста­вят на кон­вей­ер­ную ленту сле­ду­ю­щим об­ра­зом: стро­ит­ся по­сле­до­ва­тель­ность 2 · N, все числа дан­ные в парах сор­ти­ру­ют­ся по воз­рас­та­нию в этой по­сле­до­ва­тель­но­сти от наи­мень­ше­го к наи­боль­ше­му.

Если ми­ни­маль­ное время  — время шли­фов­ки, то де­таль ста­вит­ся в первую сво­бод­ную ячей­ку с на­ча­ла.

Если ми­ни­маль­ное время  — время по­крас­ки, де­таль ста­вит­ся в первую сво­бод­ную ячей­ку с конца.

Если ми­ни­маль­ное число время окра­ши­ва­ния или шли­фов­ки уже рас­смот­рен­ной де­та­ли, такое время иг­но­ри­ру­ет­ся.

По­лу­ча­ет­ся за­пол­нен­ная лента об­ра­бот­ки.

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

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

Опре­де­ли­те номер по­след­ней де­та­ли, по­став­лен­ной на кон­вей­ер и ко­ли­че­ство де­та­лей от­шли­фо­ван­ных до неё.

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

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

В пер­вой стро­ке вход­но­го файла на­хо­дит­ся число 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 де­та­лей долж­ны быть от­шли­фо­ва­ны и окра­ше­ны. Для каж­дой де­та­ли из­вест­но время её шли­фов­ки и время окра­ши­ва­ния. Де­та­ли про­ну­ме­ро­ва­ны на­чи­ная с еди­ни­цы. Па­рал­лель­ная об­ра­бот­ка де­та­лей не преду­смот­ре­на.

На ленте транс­портёра име­ет­ся N мест для каж­дой из N де­та­лей.

На ленте транс­портёра де­та­ли рас­по­ла­га­ют по сле­ду­ю­ще­му ал­го­рит­му:

— все 2N чисел, обо­зна­ча­ю­щих время окра­ши­ва­ния и шли­фов­ки для N де­та­лей, упо­ря­до­чи­ва­ют по воз­рас­та­нию;

— если ми­ни­маль­ное число в этом упо­ря­до­чен­ном спис­ке  — это время шли­фов­ки кон­крет­ной де­та­ли, то де­таль раз­ме­ща­ют на ленте транс­портёра на пер­вое сво­бод­ное место от её на­ча­ла;

— если ми­ни­маль­ное число  — это время окра­ши­ва­ния, то де­таль раз­ме­ща­ют на пер­вое сво­бод­ное место от конца ленты транс­портёра;

— если число обо­зна­ча­ет время окра­ши­ва­ния или шли­фов­ки уже рас­смот­рен­ной де­та­ли, то его не при­ни­ма­ют во вни­ма­ние.

Этот ал­го­ритм при­ме­ня­ет­ся по­сле­до­ва­тель­но для раз­ме­ще­ния всех N де­та­лей.

Опре­де­ли­те номер по­след­ней де­та­ли, для ко­то­рой будет опре­де­ле­но её место на ленте транс­портёра, и ко­ли­че­ство де­та­лей, ко­то­рые будут от­шли­фо­ва­ны до неё.

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

В пер­вой стро­ке вход­но­го файла на­хо­дит­ся на­ту­раль­ное число N (N ≤ 1000)

— ко­ли­че­ство де­та­лей. Сле­ду­ю­щие N строк со­дер­жат пары чисел, обо­зна­ча­ю­щих со­от­вет­ствен­но время шли­фов­ки и время окра­ши­ва­ния кон­крет­ной де­та­ли (все числа

— на­ту­раль­ные, раз­лич­ные).

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

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

5

30 50

100 155

150 170

10 160

120 55

При таких ис­ход­ных дан­ных по­ря­док рас­по­ло­же­ния де­та­лей на ленте транс­портёра сле­ду­ю­щий: 4, 1, 2, 3, 5. По­след­ней займёт своё место на ленте транс­портёра де­таль 3. При этом до неё будут от­шли­фо­ва­ны три де­та­ли.

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

Гео­де­зист из­ме­ря­ет вы­со­ту над уров­нем моря (в мил­ли­мет­рах) от­но­си­тель­но уров­ня на­ча­ла до­ро­ги, для каж­дой из N её мет­ро­вых от­ме­ток. Ну­ме­ра­ция от­ме­ток на­чи­на­ет­ся с еди­ни­цы.

Про­ек­ти­ров­щи­кам не­об­хо­ди­мо вы­брать уча­сток до­ро­ги дли­ной не менее К мет­ров, на ко­то­ром зна­че­ние суммы всех высот, вы­ра­жен­ное в мил­ли­мет­рах, мак­си­маль­но. Это зна­че­ние на­зы­ва­ет­ся оцен­кой участ­ка до­ро­ги. На­ча­ло и конец ис­ко­мо­го участ­ка сов­па­да­ют с мет­ро­вы­ми от­мет­ка­ми на до­ро­ге. На­ча­лом участ­ка счи­та­ет­ся мет­ро­вая от­мет­ка до­ро­ги с мень­шим но­ме­ром.

Опре­де­ли­те две мет­ро­вые от­мет­ки до­ро­ги так, чтобы рас­сто­я­ние между ними было не менее К мет­ров, а оцен­ка со­от­вет­ству­ю­ще­го участ­ка до­ро­ги  — мак­си­маль­но воз­мож­ной. Ука­жи­те в от­ве­те най­ден­ное чис­ло­вое зна­че­ние мак­си­маль­ной оцен­ки, вы­ра­жен­ное в мил­ли­мет­рах.

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

Даны два вход­ных файла (файл А и файл В), каж­дый из ко­то­рых в пер­вой стро­ке вход­ных дан­ных задаётся про­тя­жен­ность до­ро­ги N (1 ≤ N ≤ 10 000), а во вто­рой  — на­ту­раль­ное число К  — ми­ни­маль­но до­пу­сти­мое рас­сто­я­ние (в мет­рах) между двумя от­мет­ка­ми до­ро­ги (N > К).

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

В от­ве­те ука­жи­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла А, затем  — для файла В.

Ответ:

Дана по­сле­до­ва­тель­ность целых чисел. Рас­сто­я­ние между эле­мен­та­ми по­сле­до­ва­тель­но­сти  — это раз­ность их по­ряд­ко­вых но­ме­ров. На­при­мер, если два эле­мен­та стоят в по­сле­до­ва­тель­но­сти рядом, рас­сто­я­ние между ними

равно 1, если два эле­мен­та стоят через один  — рас­сто­я­ние равно 2 и так далее.

Не­об­хо­ди­мо вы­брать из по­сле­до­ва­тель­но­сти три числа так, чтобы ми­ни­маль­ное рас­сто­я­ние между вы­бран­ны­ми чис­ла­ми было не мень­ше K, а их сумма была мак­си­маль­но воз­мож­ной.

В от­ве­те за­пи­ши­те най­ден­ную сумму

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

Пер­вая стро­ка вход­но­го файла со­дер­жит целое число K  — па­ра­метр для опре­де­ле­ния рас­сто­я­ния, вто­рая стро­ка со­дер­жит число N  — общее ко­ли­че­ство чисел в на­бо­ре (1 < 2K < N). Каж­дая из сле­ду­ю­щих N строк со­дер­жит одно число, не пре­вы­ша­ю­щее по мо­ду­лю 10⁷.

При­мер вход­но­го файла:

2

6

6

7

8

2

3

5

Из этого файла в со­от­вет­ствии с усло­ви­я­ми можно вы­брать числа 7, 8 и 5. Мак­си­маль­ное рас­сто­я­ние в дан­ном слу­чае равно 4 (между чис­ла­ми 7 и 5). Числа 6, 7 и 8 взять нель­зя, так как мак­си­маль­ное рас­сто­я­ние в этом слу­чае равно 2, а по усло­вию оно долж­но быть не мень­ше 4. В от­ве­те для этого при­ме­ра надо на­пи­сать число 20.

Вам даны два вход­ных файла (A и B), каж­дый из ко­то­рых имеет опи­сан­ную выше струк­ту­ру. В от­ве­те ука­жи­те два числа: сна­ча­ла тре­бу­е­мую сумму для файла A, затем  — для файла B.

Ответ:

За­да­ние вы­пол­ня­ет­ся с ис­поль­зо­ва­ни­ем при­ла­га­е­мых фай­лов.

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

Опре­де­ли­те два таких пе­ре­дан­ных числа, чтобы между мо­мен­та­ми их пе­ре­да­чи про­шло не менее мин., а их про­из­ве­де­ние было мак­си­маль­но воз­мож­ным. В от­ве­те за­пи­ши­те  — най­ден­ное про­из­ве­де­ние.

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

Даны два вход­ных файла (файл А и файл В), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит на­ту­раль­ное число K  — ми­ни­маль­ное ко­ли­че­ство минут, ко­то­рое долж­но прой­ти между  — двумя пе­ре­да­ча­ми по­ка­за­ний, а во вто­рой  — ко­ли­че­ство пе­ре­дан­ных по­ка­за­ний N (1 ≤  N ≤ 10 000 000, N > K). В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся одно целое число, по мо­ду­лю не пре­вы­ша­ю­щее 100 000, обо­зна­ча­ю­щее чис­ло­вое зна­че­ние за­ря­да ча­стиц в ми­ну­ту.

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

За­пи­ши­те в от­ве­те два числа: сна­ча­ла зна­че­ние ис­ко­мой ве­ли­чи­ны для файла A, затем  — для файла B.

Ответ: