E. Жорж ба картууд

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

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

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

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

Жорж муур тоглох үнэхээр дуртай.

Виталий Жоржийн өмнө $n$ картуудыг дараалан тавив. Карт бүр дээр нэг бүхэл тоо бичигдсэн бөгөөд эдгээр тоонууд бүгд ялгаатай байна. Картуудыг зүүнээс баруун тийш $1$-с $n$ хүртэл дугаарласан гэж бодъё. Тэгвэл зүүн талаасаа $i$-р картан дээр $p_{i}$ ($1 ≤ p_{i} ≤ n$) тоо бичигдсэн.

Виталий эгнээний зүүн талын яг $k$ картуудыг байлгахыг хүссэн. Мөн тэр зүүнээсээ $i$-р картан дээр $b_{i}$ тоог бичихийг хүссэн. Виталий Жоржд устгах үйлдлийг $n - k$ удаа ашиглан шаардлагатай дарааллыг гаргаж авах даалгавар өгөв.

Жорж нэг устгах үйлдлээр $w$ ($1 ≤ w$; $w$ нь одоогийн дараалсан картуудын тооноос ихгүй) үргэлжилсэн картууд (картуудын үргэлжилсэн дэд хэсэг) сонгож чадна. Эдгээр картууд дээр $x_{1}, x_{2}, ..., x_{w}$ (зүүнээс баруун тийш) тоонууд бичигдсэн гэж үзье. Үүний дараа Жорж $j$ $(1 ≤ j ≤ w)$ бүрийн хувьд $x_{i} ≤ x_{j}$ байх $x_{i}$ картыг устгаж чадна. Тодорхойлсон үйлдлийн дараа Жорж $w$ ширхэг хиам авна.

Жорж бодов: Хэрвээ тэр зорилгодоо хүрч, оновчтой сайн ажиллаж чадвал хамгийн ихдээ хэдэн хиам авах бол? Асуултынхаа хариуг олоход Жоржд туслана уу!

Оролт

Эхний мөр нь $n$ ба $k$ ($1 ≤ k ≤ n ≤ 10^{6}$) бүхэл тоонуудаас бүрдэнэ. Эдгээр нь эхний болон эцсийн картуудын тоо.

Хоёр дахь мөр нь $n$ ширхэг ялгаатай, зайгаар тусгаарлагдсан $p_{1}, p_{2}, ..., p_{n}$ ($1 ≤ p_{i} ≤ n$) бүхэл тоонуудыг агуулна. Эхний картуудын дараалал.

Гурав дахь мөр нь $k$ ($1 ≤ k ≤ n ≤ 10^{6}$) ширхэг ялгаатай, зайгаар тусгаарлагдсан $b_{1}, b_{2}, ..., b_{k}$ бүхэл тоонуудыг агуулна. Энэ нь чиний авах хэрэгтэй картуудын дараалал. Устгах үйлдлийг $n - k$ удаа ашиглан өгөгдсөн дарааллыг гаргаж авах боломжтой байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Хэрвээ Жорж оновчтой сайн ажиллаж чадвал, түүний авч чадах хиамны хамгийн их тоо юм.

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

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

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