uses heap;

fn main
[
	const d2dx := [ 0, 1, 0, -1 ];
	const d2dy := [ -1, 0, 1, 0 ];
	var lines := list_break_to_lines(read_lazy(h[0]));
	const x := len(lines[0]);
	const y := len(lines);
	var a := list_to_array([x, y], list_join(lines, ""));
	a := map(a, lambda(x : byte) [ return x - '0'; ]);
	a := array_flatten(a);
	var min_hl := array_fill(-1, [x, y, 4]);
	var pending := heap_from_list([ mktuple4(0, 0, 0, 1), mktuple4(0, 0, 0, 2) ]);
	while heap_is_nonempty~inline(pending) do [
		var s : tuple4(int, int, int, int);
		pending, s := heap_extract~inline(pending);
		if min_hl[s.v2, s.v3, s.v4] <> -1 then
			continue;
		min_hl[s.v2, s.v3, s.v4] := s.v1;
		if s.v2 = x - 1, s.v3 = y - 1 then [
			write(h[1], ntos(s.v1) + nl);
			break;
		]
		var dx := d2dx[s.v4];
		var dy := d2dy[s.v4];
		var xp := s.v2;
		var yp := s.v3;
		var loss := s.v1;
		for moves := 0 to 10 do [
			xp += dx;
			yp += dy;
			if xp < 0 or xp >= x or yp < 0 or yp >= y then
				break;
			loss += a[xp, yp];
			if moves >= 3 then [
				if min_hl[xp, yp, s.v4 xor 1] = -1 then
					pending := heap_insert~inline(pending, mktuple4(loss, xp, yp, s.v4 xor 1));
				if min_hl[xp, yp, s.v4 xor 3] = -1 then
					pending := heap_insert~inline(pending, mktuple4(loss, xp, yp, s.v4 xor 3));
			]
		]
	]
]