Вход­ной файл со­дер­жит за­яв­ки пас­са­жи­ров, же­ла­ю­щих сдать свой багаж в ка­ме­ру хра­не­ния, со­сто­я­щей из мно­же­ства ячеек. Для каж­дой ячей­ки из­вест­на сто­и­мость хра­не­ния од­но­го ба­га­жа.

В за­яв­ке ука­за­ны время сдачи ба­га­жа (в ми­ну­тах от на­ча­ла суток) и время хра­не­ния ба­га­жа в ячей­ке. Багаж каж­до­го пас­са­жи­ра за­ни­ма­ет ровно одну ячей­ку и может по­ме­стить­ся в любой ячей­ке. Если в мо­мент сдачи ба­га­жа сво­бод­ных ячеек нет, пас­са­жир ухо­дит. Если сво­бод­ных ячеек не­сколь­ко, пас­са­жир вы­би­ра­ет сво­бод­ную ячей­ку с наи­мень­шей сто­и­мо­стью, а среди ячеек с оди­на­ко­вой сто­и­мо­стью  — ячей­ку с наи­мень­шим но­ме­ром. Раз­ме­ще­ние ба­га­жа в ячей­ке или её осво­бож­де­ние про­ис­хо­дит мо­мен­таль­но, после осво­бож­де­ния сле­ду­ю­щий пас­са­жир может сразу же за­нять эту ячей­ку.

Опре­де­ли­те сумму, ко­то­рая по­тре­бу­ет­ся для хра­не­ния ба­га­жа тех пас­са­жи­ров, ко­то­рые смо­гут оста­вить свой багаж в те­че­ние 15 ч (от на­ча­ла суток), а также номер ячей­ки, в ко­то­рой будет раз­мещён по­след­ний сдан­ный багаж за 15 ч.

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

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

Каж­дая из по­сле­ду­ю­щих K строк со­дер­жит два на­ту­раль­ных числа, не пре­вы­ша­ю­щих 1440: ука­зан­ное в за­яв­ке время раз­ме­ще­ния ба­га­жа в ячей­ке (в ми­ну­тах от на­ча­ла суток) и срок хра­не­ния ба­га­жа (в ми­ну­тах). Га­ран­ти­ру­ет­ся, что время раз­ме­ще­ния ба­га­жа любых двух пас­са­жи­ров раз­лич­но.

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

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

2 5

70

60

30 30

40 960

59 1

61 939

1010 430

При­мер ор­га­ни­за­ции дан­ных при­ведён для двух ячеек и пяти пас­са­жи­ров.

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

Ответ:

Вход­ной файл со­дер­жит за­яв­ки пас­са­жи­ров, же­ла­ю­щих сдать свой багаж в ка­ме­ру хра­не­ния, со­сто­я­щей из мно­же­ства ячеек. Для каж­дой ячей­ки из­вест­на сто­и­мость хра­не­ния од­но­го ба­га­жа.

В за­яв­ке ука­за­ны время сдачи ба­га­жа (в ми­ну­тах от на­ча­ла суток) и время хра­не­ния ба­га­жа в ячей­ке. Багаж каж­до­го пас­са­жи­ра за­ни­ма­ет ровно одну ячей­ку и может по­ме­стить­ся в любой ячей­ке. Если в мо­мент сдачи ба­га­жа сво­бод­ных ячеек нет, пас­са­жир ухо­дит. Если сво­бод­ных ячеек не­сколь­ко, пас­са­жир вы­би­ра­ет сво­бод­ную ячей­ку с наи­мень­шей сто­и­мо­стью, а среди ячеек с оди­на­ко­вой сто­и­мо­стью  — ячей­ку с наи­мень­шим но­ме­ром. Раз­ме­ще­ние ба­га­жа в ячей­ке или её осво­бож­де­ние про­ис­хо­дит мо­мен­таль­но, после осво­бож­де­ния сле­ду­ю­щий пас­са­жир может сразу же за­нять эту ячей­ку.

Опре­де­ли­те сумму, ко­то­рая по­тре­бу­ет­ся для хра­не­ния ба­га­жа тех пас­са­жи­ров, ко­то­рые смо­гут оста­вить свой багаж в те­че­ние 18 ч (от на­ча­ла суток), а также номер ячей­ки, в ко­то­рой будет раз­мещён по­след­ний сдан­ный багаж за 18 ч.

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

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

Каж­дая из по­сле­ду­ю­щих K строк со­дер­жит два на­ту­раль­ных числа, не пре­вы­ша­ю­щих 1440: ука­зан­ное в за­яв­ке время раз­ме­ще­ния ба­га­жа в ячей­ке (в ми­ну­тах от на­ча­ла суток) и срок хра­не­ния ба­га­жа (в ми­ну­тах). Га­ран­ти­ру­ет­ся, что время раз­ме­ще­ния ба­га­жа любых двух пас­са­жи­ров раз­лич­но.

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

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

2 5

70

60

30 30

40 960

59 1

61 939

1010 430

При­мер ор­га­ни­за­ции дан­ных при­ведён для двух ячеек и пяти пас­са­жи­ров.

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

Ответ: