B. Дзи өөрчлөлтөнд дуртай

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

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

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

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

Дзи тоглох дуртайг бид мэднэ. Нэг өдөр Дзи $n × m$ матрицаар тоглохоор шийдсэн. Илүү тодорхой хэлвэл тэр яг $k$ үйлдэл хийж матрицыг өөрчлөхөөр шийдсэн.

Өөрчлөлт бүр дараах хоёрын нэг байна:

  1. Матрицын аль нэг мөрийг сонгоод, тухайн мөрийн элемент бүрийг $p$-р бууруулна. Энэ үйлдэл нь Дзид мөрийг бууруулахаас өмнөх элементүүдийн нийлбэртэй тэнцүү хэмжээний сэтгэл ханамжийг авчирна.
  2. Матрицын аль нэг баганыг сонгоод, тухайн баганын элемент бүрийг $p$-р бууруулна. Энэ үйлдэл нь Дзид баганыг бууруулахаас өмнөх элементүүдийн нийлбэртэй тэнцүү хэмжээний сэтгэл ханамжийг мөн авчирна.

Дзи мэдэхийг хүссэн: Яг $k$ өөрчлөлтийг хийсний дараах сэтгэл хаманжийн утга хамгийн ихдээ хэд байх бол? Үүнийг тооцоолоход нь түүнд туслана уу.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан $n, m, k$ and $p$ $(1 ≤ n, m ≤ 10^{3}; 1 ≤ k ≤ 10^{6}; 1 ≤ p ≤ 100)$ бүхэл тоонуудыг агуулна.

Дараагийн $n$ мөр бүр нь $a_{ij}-г (1 ≤ a_{ij} ≤ 10^{3})$ илэрхийлсэн $m$ бүхэл тоонуудыг агуулна. Эдгээр нь матрицын одоогийн мөрийн элементүүд.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Дзигийн авч болох хамгийн их сэтгэл ханамжийн утга.

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

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

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

Тэмдэглэл

Эхний жишээнд бид дараах өөрчлөлтийг хийж чадна: багана 2, мөр 2. Үүний дараах матриц:

1 1  
0 0

Хоёр дахь жишээнд бид дараах өөрчлөлтийг хийж чадна: багана 2, мөр 2, мөр 1, багана 1, багана 2. Үүний дараах матриц:

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