B. Хүлэмжний үр ашиг

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

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

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

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

Эмускалд бол шуналтай тариачин мөн дэлхийн хамгийн урт хүлэмжийг эзэмшдэг ба уг хүлэмж нь хягааргүй урт.

Хэдэн жилийн турш Эмускалд хүлэмждээ 1-с $m$ хүртэл дугаарлагдсан $m$ ялгаатай төрлийн $n$ ургамал тарьсан. Түүний хүлэмж нь маш нарийхан бөгөөд хязгааргүй урт шулуунаар дүрсэлж болох ба ургамал бүр уг шулууны нэг цэг дээр байрлана.

Эмускалд төрөл бүрийн ургамалууд ялгаатай температурт ургадаг гэдгийг мэдсэн ба хүлэмжийг $m$ хэсэгт хуваах $m - 1$ тусгаарлагч байрлуулахыг хүсч байна. Хэсгүүдийг зүүнээс баруун тийш 1-с $m$ хүртэл дугаарлах ба хэсэг бүрт нэг л төрлийн ургамал байна. Тусгаарлагчуудыг дурын байдлаар байрлуулж болох боловч төгсгөлд нь $i$-р төрлийн ургамалууд зүүнээсээ $i$-р хэсэгт байрлах ёстой.

Мэдээж ийм замаар тусгаарлагчуудыг байрлуулах үргэлж боломжтой байхгүй ба Эмускалд ургамалуудынхаа заримыг нь дахин байрлуулах хэрэгтэй болсон. Тэр ургамал бүрийг байрлалаас нь авч хүлэмжийн ургамалгүй байгаа дурын байрлалд (дурын бодит координат) байрлуулж болно.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$ ба $m$ ($1 ≤ n, m ≤ 5000$, $n ≥ m$) байх буюу нийт ургамалуудын тоо болон ургамалын төрлүүдийн тоо байна. Дараагийн $n$ мөр бүрт зайгаар тусгаарлагдсан хоёр тоо байх буюу бүхэл тоо $s_{i}$ ($1 ≤ s_{i} ≤ m$) болон бодит тоо $x_{i}$ ($0 ≤ x_{i} ≤ 10^{9}$) байх ба $i$-р ургамалын төрлийн дугаар болон байрлал байна. $x_{i}$ бүр цэгийн ард 6-с ихгүй цифр агуулна.

Бүх $x_{i}$ ялгаатай байх ба төрөл бүрээс ядаж нэг ургамал байна; Ургамалуудыг зүүнээс баруун тийш дараалалтай өгөх буюу тэдний $x_{i}$ координатын өсөх дарааллаар өгнө $(x_{i} < x_{i + 1}, 1 ≤ i < n)$.

Гаралт

Байрлалыг нь солих ургамалуудын хамгийн бага тоог илэрхийлэх бүхэл тоог нэг мөрөнд хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 2
2 1
1 2.0
1 3.100
Гаралт
1
Оролт
3 3
1 5.0
2 5.5
3 6.0
Гаралт
0
Оролт
6 3
1 14.284235
2 17.921382
1 20.328172
3 20.842331
1 25.790145
1 27.204125
Гаралт
2

Тэмдэглэл

Эхний жишээн дээр Эмускалд эхний ургамалыг сүүлийн ургамалын баруун талд байрлуулж болно, ингээд хариулт 1 байна.

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

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