B. Жорж ба раунд

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

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

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

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

Жорж Codesecrof раундыг бэлдэхээр шийдсэн ба тиймээс тэрээр уг раундад зориулан $m$ ширхэг бодлого бэлджээ. Бодлогуудыг $1$-ээс $m$ хүртэлх бүхэл тоонуудаар дугаарлая. Жорж $i$-дахь бодлогын төвөгтэй байдлыг бүхэл тоо $b_{i}$-аар тооцжээ.

Уг раундыг гоё болгохын тулд тэрээр дор хаяж $n$ бодлого бэлдсэн байх хэрэгтэй юм. Мөн түүнчлэн тэрээр дор хаяж нэг ширхэг төвөгтэй байдал нь $a_{1}$-тай тэнцүү бодлого, дор хаяж нэг ширхэг төвөгтэй байдал нь $a_{2}$-тай тэнцүү бодлого, ..., болон дор хаяж нэг ширхэг төвөгтэй байдал нь $a_{n}$-тай тэнцүү бодлоготой байх хэрэгтэй юм. Мэдээж хэрэг уг раунд нь өөр төвөгтэй байдлууд бүхий бодлогуудтай байж болно.

Жорж тааруухан уран сэтгэмжтэй нэгэн бөгөөд түүний хувьд шинэ бодлого зохион үүнийгээ бэлдэхээс илүүтэйгээр аль хэдийн бэлдсэн бодлогоо хялбарчлах нь амар байв. Жорж бодлогуудыг хялбарчлахдаа үнэхээр гарамгай ба тэрээр оролтын хязгаарыг өөрчлөх замаар төвөгтэй байдал нь $c$ байх аль хэдийн бэлдсэн байгаа ямар ч бодлогыг төвөгтэй байдал нь ямар ч эерэг бүхэл $d$ ($c ≥ d$) байх бодлого болгон хялбарчилж чадна.

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

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 3000$) өгөгдөх ба эдгээр нь гоё раундад байх бодлогуудын хамгийн бага тоо болон Жорж-ын бэлдсэн бодлогуудын тоог илэрхийлнэ. 2-дахь мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{1} < a_{2} < ... < a_{n} ≤ 10^{6}$) өгөгдөх ба эдгээр нь гоё раундын бодлогуудын төвөгтэй байдлуудын шаардлагуудыг илэрхийлнэ. 3-дахь мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд $b_{1}, b_{2}, ..., b_{m}$ ($1 ≤ b_{1} ≤ b_{2}... ≤ b_{m} ≤ 10^{6}$) өгөгдөх ба эдгээр нь Жорж-ын бэлдсэн бодлогуудын төвөгтэй байдлуудыг илэрхийлнэ.

Гаралт

Уг бодлогын хариулт болох ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3 5
1 2 3
1 2 2 3 3
Гаралт
0
Оролт
3 5
1 2 3
1 1 1 1 1
Гаралт
2
Оролт
3 1
2 3 4
1
Гаралт
3

Тэмдэглэл

Эхний жишээнд бэлдсэн бодлогуудын олонлог нь гоё раундын шаардлагыг хангах юм.

2-дахь жишээнд гоё раунд болгохын тулд $2$ болон $3$ гэсэн төвөгтэй байдлуудтай 2 бодлого бэлдэхэд хангалттай.

3-дахь жишээнд хэрэв $2, 3, 4$ гэсэн төвөгтэй байдлуудтай 3-н нэмэлт бодлого бэлдвэл маш амархан гоё раунд болгох юм.

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