import java.io.*; import java.util.*; public class Main { private static class Pair { String psf; int i; int j; public Pair(String psf, int i, int j) { this.psf = psf; this.i = i; this.j = j; } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int m = Integer.parseInt(br.readLine()); int[][] arr = new int[n][m]; for (int i = 0; i < n; i++) { String str = br.readLine(); for (int j = 0; j < m; j++) { arr[i][j] = Integer.parseInt(str.split(" ")[j]); } } int dp[][] = new int[m][n]; //last cell dp[m-1][n-1] = arr[m-1][n-1]; //last row for(int j = n-2 ; j >= 0 ; j--) dp[m-1][j] = dp[m-1][j+1] + arr[m-1][j]; //last col for(int i = m-2 ; i >=0 ; i--) dp[i][n-1] = dp[i+1][n-1] + arr[i][n-1]; //rest of the matrix for(int i = m -2 ; i >= 0 ;i--){ for(int j = n-2 ; j >= 0 ;j--){ dp[i][j] = Math.min(dp[i][j+1],dp[i+1][j]) ; //adding your cell's cost dp[i][j] += arr[i][j]; } } //answer stored in dp[0][0] System.out.println(dp[0][0]); //now we will use BFS to find all paths of minimum cost BFS(dp); } public static void BFS(int[][] dp){ ArrayDeque<Pair> q = new ArrayDeque<>(); q.add(new Pair("" , 0 , 0)); //adding first element while(q.size()>0){ Pair rem = q.removeFirst(); //if we have arrived at the last element if(rem.i ==dp.length-1 && rem.j == dp[0].length-1) System.out.println(rem.psf); //if last row we can move only right else if(rem.i == dp.length - 1) q.add(new Pair (rem.psf + "H", rem.i, rem.j+1)); //if last col we can move only down else if(rem.j == dp[0].length - 1) q.add(new Pair(rem.psf + "V", rem.i+1, rem.j)); //if we are in rest of the matrix else{ //if horizontal element is smallest if(dp[rem.i][rem.j+1] < dp[rem.i+1][rem.j]) q.add(new Pair (rem.psf + "H", rem.i, rem.j+1)); //if vertical element is smallest else if(dp[rem.i+1][rem.j] < dp[rem.i][rem.j+1]) q.add(new Pair(rem.psf + "V", rem.i+1, rem.j)); //if both are equal else{ q.add(new Pair(rem.psf + "V", rem.i+1, rem.j)); q.add(new Pair (rem.psf + "H", rem.i, rem.j+1)); } } } } }