D. Нууцлаг бэлэг

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

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

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

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

Петр Австралид байгаа найздаа төрсөн өдрийн бэлэг болгож ил захидал явуулахыг хүсчээ. Ингээд тэрбээр өөрийнхөө бэлгийг нууцлаг болгохын тулд $Хэлхээ$ хийхээр болжээ. $Хэлхээ$ гэдэг нь $A={a_1, a_2, ... , a_n}$ гэх дугтуйнуудын дараалыг хэлэх бөгөөд $i$-р дугтуйны урт ба өргөн нь $i-1$-р дугтуйны урт, өргөнөөс харгалзан эрс их байх ёстой.

Петр өөртөө байгаа дугтуйнууд дундаас хамгийн олныг оролцуулж $Хэлхээ$ үүсгэхийг хүсч байгаа бөгөөд, хамгийн дотор талын дугтуйн дотор ил захидал багтах ёстой юм. Хэрвээ ил захидлын урт, өргөн нь хамгийн дотор талын дугтуйны урт, өргөнөөс бага байвал түүнд багтана гэж үзнэ. Захидал болон дугтуйнуудыг нугалж болохгүй.

Петрт маш олон дугтуй байгаа боловч цаг бага байгаа учир танд энэ даалгаврыг өгсөн байна.

Оролт

Эхний мөр нь Петрт байгаа дугтуйн тоо $n$, ил захидлын урт, өргөнийг илэрхийлэх $w, h$ ($1 ≤ n ≤ 5000$, $1 ≤ w,h ≤ 10^6$) байна. Дараагийн $n$ мөр бүрт $i$-р дугтуйны урт, өргөн болох $w_i$ ба $h_i$ ($1 ≤ w_i, h_i ≤ 10^6$) өгөгдөнө.

Гаралт

Гаралтын эхний мөрт $Хэлхээ$нд агуулагдах дугтуйн тоо. Дараагийн мөрөнд хамгийн жижиг дугтуйнаас эхлээд дугтуйнуудын дугаарыг хэвлэнэ. Ил захидал хамгийн жижиг дугтуйнд багтаж байх ёстойг санаарай! Олон хариутай бол алийг нь ч хэвлэсэн болно.

Хэрвээ ил захидал аль ч дугтуйнд багтахгүй бол $0$ гэсэн ганц мөр хэвлэнэ.

Орчуулсан: zoloogg

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

Оролт
2 1 1
2 2
2 2
Гаралт
1
1 
Оролт
3 3 3
5 4
12 11
9 8
Гаралт
3
1 3 2 
Сэтгэгдлүүдийг ачааллаж байна...