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

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

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

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

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

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

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

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