Ели се пресели в Манхатън. За нея това е рай. Пълно е с молове и магазини, които тя обожава! Както може би знаете, Махнатън е известен с правите си улици. Затова можем да го представим като правоъгълник с N улици в посока запад-изток и M улици север-юг, като на всяка пресечка се намира по един мол. Ели за съжаление не може да мине покрай мол и да не си купи нещо. За щастие, обаче, тя е толкова редовен клиент, че в някои от тях й правят толкова огромни отстъпки, че на практика й дават пари за да вземе стоки. Можем да направим оценка на моловете, като "колко пари ще даде Ели ако мине оттам". В моловете, където й дават пари, това число може да е отрицателно.

Ели мисли за финансовото си положение, както и финансовото положение мисли за Ели. Тя е решила да избере такова подмножество от молове, че:

• Да може да стигне от всеки от избраните молове до всеки друг, като не минава през мол, който е извън избраното подмножеството. Поради правите улици, тя може да се движи само на север, юг, изток и запад.
• Сумата, която ще даде ако мине през всички избрани молове по веднъж е минимална.

Забележете, че тя може да избере да не мине през никой мол, в който случай сумата ще е 0. От вас се иска да напишете програма, която по дадена информация за моловете намира минималната сума, която може да плати Ели, ако избере оптималното тяхно подмножество. На първия ред на стандартния вход ще бъдат зададени двете цели числа N и M – съответно броят редове (хоризонтални улици) и броят колони (вертикални улици), където тя обикновено се подвизава. На следващите N реда ще има по M цели числа A_ij, като това на i-ти ред и j-та колона задава парите, които тя ще даде (или вземе) в съответния мол. На стандартния изход изведете едно единствено цяло число – минималната сума, която Ели може да даде. Това число ще е или отрицателно или нула, тъй като всяко положително число тя може да "подобри" като не избере нито един мол.

• 1 ≤ N ≤ 20
• 1 ≤ M ≤ 9
• -1000 ≤ A_ij ≤ 1000

Примерен Вход	Примерен Изход
3 5 1 -4 5 -3 -2 3 1 -2 0 1 -2 4 7 -1 -2	-13