E. Сиел ба Гондола завь

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

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

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

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

Сиел үнэг тоглоомын парк-д байв. Одоо тэрээр Феррис дугуйн урд дараалалд оочирлон зогсож байв. Уг дараалалд $n$ хүн (үнэг гэсэн ч болно) зогсож байв: бид 1-дэх хүн гэдгийг уг дарааллын эхний хүн гэж үзэх ба $n$-дэх хүн гэдгийг уг дарааллын сүүлийн хүн гэж үзнэ.

Нийт $k$ ширхэг гондола завь байх ба бид эдгээр завьнуудыг дараах байдлаар хуваарилах юм:

  • Эхний завь ирэхэд уг дарааллын эхэнд байрлах $q_{1}$ хүн уг завинд сууна.
  • Дараа нь 2-дахь завь ирэхэд үлдсэн дарааллын эхэнд байрлах $q_{2}$ хүн уг завинд сууна.

    ...

  • Үлдсэн $q_{k}$ хүн сүүлийн завинд ($k$-дахь) сууна.

$q_{1}$, $q_{2}$, ..., $q_{k}$ заавал эерэг байхыг анхаарна уу. Та уг нөхцөлөөс тэнцэтгэлийг гаргаж болох ба $q_{i} > 0$ байна.

Таны мэдэж байгаачлан хүмүүс завин дээр үл таних хүмүүстэй цуг суухыг хүсэхгүй. Иймд таны даалгавар бол хүмүүсийг баяртай байлгахаар оновчтойгоор завинд хуваарилах юм (өөрөөр хэлбэл оновчтой $q$ дарааллыг олно). $i$ болон $j$ гэсэн бүх хос хүмүүсийн хувьд эдгээр хүмүүсийн бие биенээ үл таних төвшин болох $u_{ij}$ утга оршин байх юм. Та бүх $i, j$ $(1 ≤ i, j ≤ n)$-ын хувьд $u_{ij} = u_{ji}$ гэж үзэх ба $i$ $(1 ≤ i ≤ n)$ бүрийн хувьд $u_{ii} = 0$ гэж үзэх юм. Завьнуудын үл таних утга гэдэг нь уг завин дээрх бүх хос хүмүүсийн хоорондох үл таних төвшнүүдийн нийлбэр байх юм.

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

Оролт

Эхний мөрөнд дараалалд зогсож буй хүмүүсийн тоо болон завьнуудын тоог илэрхийлэх 2 бүхэл тоо $n$ болон $k$ өгөгдөх ба $1 ≤ n ≤ 4000$ , $1 ≤ k ≤ min(n, 800)$ байна. Дараагийн $n$ мөрийн мөр болгонд $n$ ширхэг бүхэл тоо өгөгдөх ба энэ нь $u$, ($0 ≤ u_{ij} ≤ 9$, $u_{ij} = u_{ji}$ ба $u_{ii} = 0$) матрицыг илэрхийлнэ.

Хурдан оролтын арга хэрэглэнэ үү. Жишээлбэл Java дээр Scanner-ын оронд BufferedReader-ын хэрэглэнэ үү.

Гаралт

Нийт үл таних утгын боломжит хамгийн бага утгыг хэвлэнэ үү.

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

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

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

Тэмдэглэл

Эхний жишээнд бид хүмүүсийг дараах байдалтай хуваарилах юм: {1, 2} нь нэг завинд суух ба {3, 4, 5} нь нөгөө завинд сууна.

2-дахь жишээнд оновчтой хариулт нь : {1, 2, 3} | {4, 5, 6} | {7, 8} байна.

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