F. Газрын тос

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

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

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

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

Газрын тосны салбарыг улсын мэдэлд шийлжүүлсэний дараа доктор Мусаддэ Персийн булангийн бүх газрын тосыг олборлохоор хэд хэдэн цооног ухахыг хүсжээ. Гэвч Персийн булан хэмжээний хувьд асар том газар нутагтай бөгөөд хэмжээлшгүй их газрын тостой байв. Тиймээс доктор Mусаддэ Персийн булангийн зөвхөн $n x m$ хэмжээтэй тэгш өнцөгт хэлбэртэй талбай дээр ажилладаг. Энэ нь тэгш өнцөгт талбайд ухсан зарим нүх хэмжээлшгүй их хэмжээний газрын тостой байхад зарим нь юу ч үгүй байдаг байв.

Нэг төгсгөлтэй хоёр сувгийг зэргэлдээ суваг гэж үзэх ба түүний жим нь $c_{1}, c_{2}, ..., c_{x}$ гэсэн дараалалтай сувгууд байх бөгөөд эдгээр нь бүгд газрын тос агуулж байх юм. Хэрэв $i$, $c_{i}$ гэсэн суваг байгаа гэж үзвэл энэ нь $c_{i - 1}$ ба $c_{i + 1}$ гэсэн сувгуудтай зэргэлдээ суваг гэж үзнэ. Хоёр суваг замаар тусгаарлагдсан бол тэдгээрийг холбоотой суваг гэнэ. Хэрэв бид тухайн нэг сувгийг ухаж газрын тос гаргаж авлаа гэхэд түүнтэй холбоотой бүх сувгуудаас газрын тос олборлох боломжтой болно гэсэн үг юм. Хоосон сувгуудыг ухах нь зөвшөрөгдөөгүй зүйл юм. Доктор Мосаддэ хоосон сувгууд нь эгнээ, мөр үүсгэдэг гэдгийг мэднэ. Хэрэв зарим сувгууд нь хоосон бол тухайн эгнээ тэр чигээрээ хоосон эсвэл тухайн мөр хоосон эсвэл аль аль нь хоосон байх юм. Доктор Мосаддэд тухайн бүсэд байгаа бүх газрын тосыг олборлохын тулд хэдэн нүх ухах ёстойг олоход тусална уу.

Оролт

Эхний мөрөнд $n$ ба $m$ ($1 ≤ n, m ≤ 100$) гэсэн хоёр эерэг бүхэл тоо байна. Хоёр дахь мөрөнд газрын тосгүй хоосон мөрний тоог илэрхийлсэн $t$ ($0 ≤ t ≤ n$) гэсэн бүхэл тоо байна. Үүний араас $t$ ширхэг ялгаатай эерэг хоосон мөрүүдийн дугаар байрлах ба энэ нь $[1, n]$ завсарт байна.
Гурав дахь мөрөнд газрын тосгүй хоосон баганы тоог илэрхийлсэн $s$ ($0 ≤ s ≤ m$) гэсэн бүхэл тоо байна. Үүний араас $s$ ширхэг ялгаатай эерэг хоосон багануудын дугаар байрлах ба энэ нь $[1, m]$ завсарт байна.
Мөрнүүд нь дээрээсээ доош $1$ to $n$ гэж эрэмбэлэгдэх бол баганууд нь зүүнээсээ баруун тийш $1$ to $m$ дугаарлагдана.

Гаралт

Доктор Моссадэ хамгийн багадаа хэдэн нүх ухах ёстой вэ? Энэ нь өгөгдсөн мөр болон баганыг арилгах замаар хэдэн талбай үүсгэж болохыг олох явдал юм.

Орчуулсан: Энхгэрэл

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

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