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, 3]);
	var pending := heap_init(tuple5(int, int, int, int, int));
	pending := heap_insert(pending, mktuple5(0, 0, 0, 0, 0));
	while heap_is_nonempty~inline(pending) do [
		var s : tuple5(int, int, int, int, int);
		pending, s := heap_extract~inline(pending);
		if min_hl[s.v2, s.v3, s.v4, s.v5] <> -1 then
			continue;
		min_hl[s.v2, s.v3, s.v4, s.v5] := s.v1;
		if s.v2 = x - 1, s.v3 = y - 1 then [
			write(h[1], ntos(s.v1) + nl);
			break;
		]
		for d := 0 to 4 do [
			var dx := d2dx[d];
			var dy := d2dy[d];
			if s.v2 + dx < 0 or s.v2 + dx >= x or
			   s.v3 + dy < 0 or s.v3 + dy >= y then
				continue;
			if d = (s.v4 xor 2) then
				continue;
			var last_d := select(d = s.v4, 0, s.v5 + 1);
			if last_d >= 3 then
				continue;
			if min_hl[s.v2 + dx, s.v3 + dy, d, last_d] <> -1 then
				continue;
			pending := heap_insert~inline(pending, mktuple5(s.v1 + a[s.v2 + dx, s.v3 + dy], s.v2 + dx, s.v3 + dy, d, last_d));
		]
	]
]