B. Цамхаг

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Та бүхний мэдэж байгаагаар, Берландын бүх хүүхдүүд шоогоор тоглох дуртай. Бяцхан Петяд ижил хэмжээтэй шооноос бүтсэн $n$ цамхаг байдаг. $i$-р цамхаг нь дээр дээрээсээ давхарласан $a_{i}$ шооноос бүрдэнэ. Петя цамхагуудын хэврэг байдлын утгыг хамгийн их болон хамгийн бага өндөртэй цамхагуудын хоорондын зөрүүгээр тодорхойлсон. Жишээ нь, хэрвээ Петя (8, 3, 2, 6, 3) өндөртэй таван шоон цамхаг барьсан бол, үүний хэврэг байдал нь 6-тай тэнцүү (хамгийн өндөр цамхагийн өндөр нь 8, хамгийн намханы өндөр 2 байна).

Хүү цамхагуудын хэврэг байдлыг аль болохоор бага байлгахыг хүсдэг. Тэр дараах үйлдлүүдийг хэд хэдэн удаа хийж чадна: Тэр өөрийн зарим цамхагийн дээд шоог аваад түүнийгээ бусад цамхагийн орой дээр байрлуулна. Ижил өндөртэй цамхагуудын дээр шоо тавьж болохгүйг анхаарна уу, учир нь энэ нь устгагдах бөгөөд Петя цагийн гарз гэж боддог.

Сургуульдаа явахаас өмнө хүүд $k$ үйлдэл гүйцэтгэх л хугацаа байна. Петя ангидаа хоцорч очихыг хүсэхгүй байгаа, тиймээс энэ даалгаврыг гүйцэтгэхэд түүнд таны тусламж хэрэгтэй.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан эерэг бүхэл $n$, $k$ хоёр тоог оруулна ($1 ≤ n ≤ 100$, $1 ≤ k ≤ 1000$). Энэ нь цамхагуудын тоо болон Петягийн хийж чадах хамгийн их үйлдлийн тоо. Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ эерэг бүхэл $a_{i}$ ($1 ≤ a_{i} ≤ 10^{4}$) тоог оруулна. Энэ бол цамхагуудын анхны өндөр юм.

Гаралт

Эхний мөрөнд зайгаар тусгаарлагдсан сөрөг биш бүхэл $s$ болон $m$ ($m ≤ k$) хоёр тоог хэвлэнэ. Эхний тоо нь хамгийн ихдээ $k$ үйлдлийг гүйцэтгэсний дараах боломжит хамгийн бага хэврэг байдлын утга бол хоёр дахь тоо нь үүнд шаардлагатай үйлдлийн тоо юм.

Дараагийн $m$ мөрөнд үйлдэл бүрийг тодорхойлсон эерэг бүхэл $i$ ба $j$ тоог хэвлэх бөгөөд эдгээр нь $1$-с $n$ завсарт оршино. Энэ нь Петя $i$-р цамхагын дээд шоог авч $j$-р ($i ≠ j$) цамхаг дээр тавьж байгааг илэрхийлнэ. Үйлдлийг гүйцэтгэх явцад зарим цамхагын өндөр тэгтэй тэнцүү болж болохыг анхаараарай. Хэрвээ боломжит хамгийн бага хэврэгтэй зөв дараалал олон байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 2
5 8 5
Гаралт
0 2
2 1
2 3
Оролт
3 4
2 2 4
Гаралт
1 1
3 2
Оролт
5 3
8 3 2 6 3
Гаралт
3 3
1 3
1 2
1 3

Тэмдэглэл

Эхний жишээнд хоёр дахь цамхагаас нэгдүгээр цамхагруу нэг шоо, гуравдугаар цамхагруу нэг шоо зөөж нийт хоёр үйлдэл хийнэ. Дараа нь бүх цамхагийн өндөр ижил буюу зургаатай тэнцүү байна.

Сэтгэгдлүүдийг ачааллаж байна...