B. Уран зургийн нэгдэл

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

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

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

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

"Kalevich амьд байна!" нэртэй олонд танигдсан уран зургийн нэгдэл нь урлагийн бүтээл (зурагнууд) хийдэг. Нэгдэл нь $n$ зураачидтай бөгөөд дараах байдлаар ажлаа зохион байгуулахаар шийдсэн.

Зураач бүр түүнд оноогдсон нэг өнгийг ашигладаг. Бүх зураачдын өнгөнүүд нь ялгаатай. Эхний зураач өнгө 1-г, хоёр дахь зураач өнгө 2-г гэх мэтчилэн ашигладаг гэж үзье. Зураг бүр бүх $n$ өнгөнүүдийг агуулсан байна. $i$-р зурагт $j$-р өнгийг $j$-р зураач нэмж зурахад $t_{ij}$ нэгж цаг зарцуулна.

Дараалал хэзээд чухал байна, тэгэхээр зураачдын ажил дараах дүрмүүдээр чиглүүлэгдсэн:

  • Зураг бүрийг эхлээд эхний зураач зурсаны дараа хоёр дахь зураач гэх мэтчилэн зурна. Энэ нь зургийг $j$-р зураач зурж дууссаны дараа $(j + 1)$-р зураачруу явж болно гэсэн үг юм ($j < n$);
  • Зураач бүр зарим нэг дарааллаар зураг дээр ажиллана: эхлээд, зураач эхний зургийг зураад, дараа нь хоёрдугаар зургийг гэх мэтчилэн зурна;
  • Зураач бүр хамгийн ихдээ нэг зураг дээр л зэрэг ажиллаж чадна. Хэдий тийм ч зураачдад ямар ч амралтын цаг хэрэггүй;
  • $j$-р зураач зургийн өөрт оноогдсон ажлыг дуусгасны дараа, даруй дараагийн зураач зургийг хүлээж авна.

Өгөгдсөн зураачид 0 цагт ажлаа эхлэх бол зураг бүрийн борлуулалтанд бэлэн болох хугацааг ол.

Оролт

Эхний мөрөнд $m, n$ ($1 ≤ m ≤ 50000, 1 ≤ n ≤ 5$) бүхэл тоонуудыг оруулна, $m$ нь зургуудын тоо, харин $n$ нь зураачдын тоо. Дараа нь зургуудын тодорхойлолтууд нэг мөрөнд нэг байна. Мөр бүр нь $n$ бүхэл $t_{i1}, t_{i2}, ..., t_{in}$ ($1 ≤ t_{ij} ≤ 1000$) тоонуудыг агуулах ба $t_{ij}$-р цаг нь $j$-р зураач $i$-р зургийг зурахад зарцуулах хугацаа юм.

Гаралт

$m$ ширхэг бүхэл тоонуудын дараалал $r_{1}, r_{2}, ..., r_{m}$ хэвлэнэ. $r_{i}$ бол $n$-р зураач $i$-р зургийг зурж дууссан цаг юм.

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

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

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