Гиоргий Тиньковидзе, работает в Министерстве инфраструктуры Грузии (inprast'rukt'uris saminist'ro). В связи с объявленным 14-го декабря решением Европейской комиссии о предоставлении Грузии статуса кандидата на вступление в Европейский союз, министерству инфраструктуры было поручено организовать информационную поддержку празднований.

Гиоргий Подворнидзе в свою очередь требуется проложить интернет кабель через весь проспект Руставели от Площади Свободы до самого памятника Шота Руставели. Длина данного участка дороги составляет $$$k$$$ метров. В распоряжении Гиоргия есть $$$n$$$ проводов, каждый из них характеризуется длиной и порядковым номером. Гиоргию требуется составить провод достаточной длины ($$$\geq k$$$ метров), при этом получившаяся перестановка из порядковых номеров проводов должна быть лексикографически как можно меньше.

К сожалению, не все так просто, как думал Гиоргий — не любую пару проводов можно соединить между собой. Для каждого провода известны типы разъемов на его концах — либо P (папа, гр. mama), либо M (мама, гр. deda). Провода могут быть как MM, так и PP, так и MP. Соединять провода можно только через различные типы разъемов на концах. Провода можно переворачивать, а итоговый провод должен получиться с разъемом P в начале и разъемом M в конце.

Помогите Гиоргию составить нужную ему цепь из проводов или скажите, что это не возможно.