D. Цэлцэгнүүрэн мангасууд

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

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

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

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

Та өмнө нь Цэлцэгнүүрэн мангасууд тоглоомыг тоглож байсан уу? Энэ даалгаварт энэ тоглоомын хялбаршуулсан нэг хэмжээст загварыг ашиглана.

Нүднүүд нь бүхэл тоон дарааллаар дугаарлагдсан хязгааргүй алаг судал байна гэж төсөөлөөд үз. Судлын зарим нүднүүдэд мангас байгаа ба үлдсэн нүднүүд нь хоосон байна. Бүх мангасыг цэлцэгнүүрээр хийсэн учраас хэрвээ хоёр мангас хөрш нүдэнд байгаа бол тэдгээр нь хоорондоо наалдана (шууд утгаараа). Үүнтэй адилаар хэрвээ хэд хэдэн мангас хөрш нүднүүдэд байгаа бол тэд бүгдээрээ хамтдаа нэг мангасуудын хэсэг болон наалдана. Бид хамтдаа наалдсан мангасуудыг мангасуудын хэсэг гэж нэрлэнэ. Хэнтэй ч наалдаагүй тусдаа мангасыг ч мөн хэсэг гэж үзнэ.

Нэг шилжилтээр тоглогч мангасуудын ямар нэг хэсгийг сонгож аваад түүнийг өөрийн гарын хөдөлгөөнөөр зүүн эсвэл баруун тийш нь түлхэнэ. Сонгосон мангасууд өөр бусад мангасуудыг (эсвэл мангасуудын хэсгийг) цохих хүртлээ гулсана.

Жишээлбэл, хэрвээ судалын $1$, $4$, $5$ нүднүүдэд гурван мангас байгаа бол зөвхөн дөрвөн боломжтой шилжилтүүд байна: $1$ нүдний мангасыг хасах хязгааргүй чиглэл рүү явуулна, $4$ ба $5$ нүднүүдийн мангасуудыг нэмэх хязгааргүй чиглэл рүү явуулна, $1$ нүдний мангасыг баруун тийш түлхэнэ (энэ нь $3$ нүдэнд зогсоно), $4$ болон $5$ нүднүүдийн мангасуудын хэсгийг зүүн тийш нь түлхэнэ ($2$ ба $3$ нүднүүдэд зогсоно).

Судлын зарим нүднүүд нь одоор тэмдэглэгдсэн. Эдгээр нь онцгой нүднүүд юм. Тоглоомын зорилго бол мангастай боломжит хамгийн олон тусгай нүднүүдийг хийх юм.

Танд судлын онцгой нүднүүдийн дугаар болон бүх мангасын анхны байрлал өгөгдөнө. Оновчтой тоглолтонд мангасууд агуулсан онцгой нүднүүдийн хамгийн их тоо хэд байх вэ?

Оролт

Эхний мөр нь $n$, $m$ $(1 ≤ n ≤ 10^{5}; 1 ≤ m ≤ 2000)$ хоёр бүхэл тоо агуулна. Эдгээр нь судал дээрх мангасуудын тоо болон онцгой нүднүүдийн тоо юм.

Хоёр дахь мөр нь $n$ ширхэг ялгаатай бүхэл тоонуудыг агуулах ба энэ нь мангасуудтай нүднүүдийн дугаар юм. Гурав дахь нүдэнд онцгой нүднүүдийн дугаар болох $m$ ялгаатай бүхэл тоонууд байна. Нүдний тоонууд нь $2*10^{5}$-с хэтрэхгүй эерэг бүхэл тоонууд байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь оновчтой тоглолтонд мангасууд агуулсан онцгой нүднүүдийн хамгийн их тоо юм.

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

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

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