B. Будилаан хутгагчид

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

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

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

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

Хаврын сайхан өдөр фермер Жоны $n$ үнээ жүчээндээ кактус хивж байна. Үнээнүүд $1$-с $n$ хүртэл шошготой ба тэднийг эрэмбэлэн зүүнээс нь $i$-р жүчээнд $i$-р үнээг байрлуулсан. Гэсэн ч Элси Бессигийн нэр алдарын гадуур сүүдэрт үүрд амьдрана гэж ойлгосныхоо дараа Будилаан хутгагчдыг цуглуулсан ба малчны үзэсгэлэнт эрэмбийг будилуулахаар төлөвлөж байна. Фермер Жон $k$ минут дуг хийж байх хооронд Элси болон Будилаан хутгагчид давталттайгаар хоёр ялгаатай жүчээ сонгоод дотор нь байгаа үнээнүүдийг солихоор төлөвлөсөн ба минут бүрт нэгээс ихгүй солилцоо хийнэ.

Нямбай будлиулагчид болох гэж Будилаан хутгагчид тэдэнд байгаа $k$ минутанд үүсгэж болох хамгийн их будлианыг мэдэхийг хүсч байна. Бид $i$-р жүчээнд байгаа үнээний шошгыг $p_{i}$ гэж тэмдэглэнэ. Үнээнүүдийн эрэмбийн будлиан нь $i < j$ ба $p_{i} > p_{j}$ байх $(i, j)$ хос тоонуудаар илэрхийлэгдэнэ.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ n, k ≤ 100 000$) байх ба харгалзан үнээнүүдийн тоо болон фермер Жоны дуг хийх хугацаа байна.

Гаралт

Будилаан хутгагчдын $k$-с ихгүй үйлдэл гүйцэтгээд хүрч чадах хамгийн их будилааныг илэрхийлэх нэг бүхэл тоог хэвлэ.

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

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

Оролт
5 2
Гаралт
10
Оролт
1 10
Гаралт
0

Тэмдэглэл

Эхний жишээн дээр Будилаан хутгагчид эхний минутанд $1$ болон $5$ жүчээнд байгаа үнээнүүдийг сольж чадна. Тэгээд хоёр дахь минутанд $2$ болон $4$ жүчээнд байгаа үнээнүүдийг солино. Энэ нь үнээнүүдийн эрэмбийг бүтэн эргүүлэх ба бидэнд нийт $10$ будилаан үүсгэж өгнө.

Хоёр дахь жишээн дээр ганцхан үнэ байгаа учир боломжит хамгийн их будилаан нь $0$ байна.

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