Category

Similar Problems

0885. Energiya maydoni

Time limit : 2000 ms
Memory limit : 128 mb

Sizga n x m lik tog’ri to’rtburchak shaklidagi maydon berilgan.  Maydonning harbir katagida butun  sonda  ifodalangan  energiya  miqdori  berilgan.  Energiya  miqdori  musbat  bo’lsa  energy oladi,  manfiy  bo’lsa  esa  yo’qotadi.  Sizning  dastlabki  energiyangiz  no’lga  teng.  Sizning maqsadingiz maksimal energiya to’plash.  Buning uchun kataklardan yurish orqali ularni to’plab chiqishingiz  mumkin.  Lekin  har  qanday  yo’l  bilan  buni  qila  olmaysiz.  Sizning  bosib o’tgan yo’lingiz  uzluksiz  va qo’shni  kataklardan  iborat  bo’lishi  kerak.  Energiya  to’plashni  istalgan katakdan boshlashingiz mumkin. Har qadamda joriy turgan katakdan qo’shni katakga o’tishingiz mumkin.  Kataklar  agar  ular  umumiy  tamonga  ega  bo’lsa  qo’shni  deb  hisoblanadi.  Bir  marta o’tilgan katakdan boshqa o’tish mumkin emas.  Yurgan vaqtda oldinga tamon yurasiz.  Yana bir sharti sizga bir martadan ko’p bo’lmagan burulishga ruxsat etiladi. Boshlang’ich katakni istalgan tamonga qarab turib boshlashingiz mumkin.  Umuman energiya maydoniga tushmasligingiz ham mumkin.

Kiruvchi ma’lumotlar

Birinchi  qatorda   butun  n  va  m  sonlari  (1≤n,m≤1000)  beriladi.  Keyingi  n qatorning  har  birida  m  ta  son  probellar  bilan  ajratilib  beriladi.  Sonlar butun va  modul  jihatdan  108 dan  oshmaydi.

Chiquvchi ma’lumotlar

Birinchi qatorda  to’lash mumkin bo’lgan maksimal energiyaning miqdorini va undan keyin buning uchun bosib o’tish kerak bo’lgan kataklarning sonini chiqaring. Keyingi  qatorlada  bu  kataklarning  kordinatalari  “i  j”  juftliksifatida,  alohida  qatorlada  bosib o’tish  tartibida  chiqaring.  Birinchi  juftlik  yo’lning  boshlang’ich  katagini  ifodalaydi.  Bunda  i–qator nomeri(1≤in), j – ustun nomeri(1≤jm). Agar optimal javob yagona bo’lmasa ulardan istalgan birini chiqaring .

Kiruvchi ma`lumotlar

Chiquvchi ma`lumotlar

1

3 4

-2 5 -4 5

1 7 1 -7

3 -2 0 -10

13 4

3 1

3 2

2 2

1 2

2

4 3

-4 1 -2

-1 5 -2

-7 -9 -3

-1 4 -2

6 2

1 2

2 2

3

2 2

2 -3

-3 2

2 1

2 2