Masala E

Xotira 256 MB Vaqt 1000 ms

Sensor Tarmog'i

"NovaTech" robotika zavodida \(N×M\) o'lchamli sensor matritsasi o'rnatilgan. Har bir \((i, j)\) sensorida joriy energiya darajasi \(a[i][j]\) saqlanadi. Zavod uzoq vaqt to'xtatib qo'yilgani sababli, ko'plab sensorlarning energiyasi pasayib ketgan — hatto ba'zilari manfiy qiymatlarda ishlayapti.

Bosh nazorat roboti Sentinel-X tizimni ishga tushirishi uchun barcha sensorlar \(K\) dan katta yoki teng energiya darajasiga ega bo'lishi shart. Sentinel-X shartni tekshirib, yetarlicha quvvat bo'lmasa jarayonni to'xtatadi.

Zavod muhandislari Q ta rejalashtirilgan quvvatlash operatsiyasini navbat bilan amalga oshirishga tayyor. Har bir operatsiyada maxsus quvvatlash stansiyasi \((r1, c1)–(r2, c2)\) to'rtburchak sohasidagi barcha sensorlarga \(V\) birlik energiya yuboradi.

Sentinel-X nechta operatsiyadan keyin tizimni ishga tushira olishini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son —\(N, M\) (sensor matritsasining o'lchamlari). \(2 ≤ N, M ≤ 1000\)

Keyingi \(N\) qatorda har birida \(M\) ta butun son — sensorlarning boshlang'ich energiya darajalari.

Keyingi qatorda ikkita butun son — \(Q\) (operatsiyalar soni) va \(K\) (kerakli minimal energiya). \(1 ≤ Q ≤ 100000\)

Keyingi \(Q\) qatorda beshta butun son \(r1, c1, r2, c2, V\) — quvvatlash operatsiyasi: \((r1, c1)–(r2, c2)\) to'rtburchakdagi har bir sensorga \(V\) energiya qo'shiladi.

\(1 ≤ V ≤ 1000\)

\(−1000 ≤ a[i][j] ≤ 1000\)

\(1 ≤ r1 ≤ r2 ≤ N, 1 ≤ c1 ≤ c2 ≤ M\)

Operatsiyalar qat'iy tartibda bajariladi

\(Q\) ta operatsiyadan keyin barcha sensorlar \(K\) dan katta yoki teng bo'lishi kafolatlangan

Chiquvchi ma'lumotlar:

Barcha sensorlar energiyasi \(K\) dan katta yoki teng bo'lishi uchun zarur bo'lgan minimal operatsiyalar sonini chiqaring.

Misollar

#	input.txt	output.txt
1	4 6 1 1 1 3 2 2 1 1 1 3 2 2 6 4 4 4 2 2 6 4 4 4 5 7 3 6 1 1 3 3 5 1 2 4 6 5 4 1 4 3 1	2
2	2 2 1 9 9 1 3 10 1 1 2 2 4 1 1 2 2 3 1 1 2 2 3	3

Izoh:

K=6. Birinchi operatsiyadan so'ng ba'zi sensorlar hali 2 da turibdi (< 6). Ikkinchi operatsiyadan so'ng barcha sensorlar ≥ 6 bo'ladi. Uchinchi operatsiya kerak emas — javob 2.