#4356. Ceoi2014 Wall

			
Input 1

3 3

1 0 0

1 0 0

0 0 1

1 4 9 4

1 6 6 6

1 2 2 9

1 1 1

4 4 4

2 4 2

6 6 6



input 2

3 3

1 0 1

0 0 0

0 1 0

2 1 1 3

5 6 1 1

2 1 1 3

2 1 1

3 4 1

4 1 1

5 1 2

			
output 1

38



output 2

22