Go: package main

import "fmt"

func main() {
	//部屋を生成
	var H int

	fmt.Scan(&H)
	room := [][4]bool{}

	for i := 0; i < H; i++ {
		room = append(room, [4]bool{})
	}

	//荷物のおけない区画を設定
	var N int
	fmt.Scan(&N)
	for i := 0; i < N; i++ {
		var x, y int
		fmt.Scan(&x, &y)
		room[y][x] = true //ものがある状態を真とする
	}
	//荷物を配置
	var count int
	for i := 0; i < 3; i++ {
		for j := 0; j < H-1; j++ {


			if !room[j][i] && !room[j+1][i] && !room[j][i+1] && !room[j+1][i+1] {
				//if i!=0&&i!=2&&j!=H-3{
				//	if !room[j+1][i-1]&&!room[j+1][i+2]{
				//		if !room[j+2][0]&&!room[j+2][1]&&!room[j+2][2]&&!room[j+2][3]{
				//			break
				//		}
				//	}
				//}
				room[j][i] = true
				room[j+1][i] = true
				room[j][i+1] = true
				room[j+1][i+1] = true
				count++
			}
		}
	}
	//for _,v:=range room{
	//	for _,v2:=range v{
	//		if !v2 {
	//			fmt.Print("◯")
	//		}else{
	//			fmt.Print("☓")
	//		}
	//	}
	//	fmt.Println()
	//}
	fmt.Println(count)
}

Python: h, n = map(int, input().split())
c = [set() for i in range(h + 1)]
for i in range(n):
    a, b = map(int, input().split())
    c[b].add(a)
c[h] = set([1, 2])
count = 0
for i in range(h - 1):
    l = c[i] | c[i + 1]
    p = None
    if l == set():
        count += 2
        c[i + 1].add(1)
        c[i + 1].add(2)
    elif 0 not in l and 1 not in l:
        p = 1
    elif 2 not in l and 3 not in l:
        p = 3
    elif 1 not in l and 2 not in l:
        p = 2
    if p:
        j = 0
        while i + j + 1 < h + 1:
            if c[i + j + 1] | c[i + j + 1] == set():
                j += 1
            else:
                j += 1
                break
        if p != 2 and 3 - p not in c[i + j + 1] and 4 - p not in c[i + j + 1]:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
            continue
        if (j - 1) % 2 or j < 2:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
print(count)

Python: h, n = map(int, input().split())
c = [set() for i in range(h + 1)]
for i in range(n):
    a, b = map(int, input().split())
    c[b].add(a)
c[h] = set([1, 2])
count = 0
for i in range(h - 1):
    l = c[i] | c[i + 1]
    p = None
    if l == set():
        count += 2
        c[i + 1].add(1)
        c[i + 1].add(2)
    elif 0 not in l and 1 not in l:
        p = 1
    elif 2 not in l and 3 not in l:
        p = 3
    elif 1 not in l and 2 not in l:
        p = 2
    if p:
        j = 0
        while True:
            if c[i + j + 1] | c[i + j + 1] == set():
                j += 1
            else:
                break
        if p != 2 and p - 1 not in c[i + j + 1] and p not in c[i + j + 1]:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
            continue
        if j % 2 or j < 2:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
print(count)

Python: h, n = map(int, input().split())
c = {i:set() for i in range(h + 1)}
for i in range(n):
    a, b = map(int, input().split())
    c[b].add(a)
c[h] = set([1, 2])
count = 0
for i in range(h - 1):
    l = c[i] | c[i + 1]
    p = None
    if l == set():
        count += 2
        c[i + 1].add(1)
        c[i + 1].add(2)
    elif 0 not in l and 1 not in l:
        p = 1
    elif 2 not in l and 3 not in l:
        p = 3
    elif 1 not in l and 2 not in l:
        p = 2
    if p:
        j = 0
        while i + j + 1 < h:
            if c[i + j + 1] == set():
                j += 1
            else:
                break
        if p != 2 and 3 - p not in c[i + j + 2] and 4 - p not in c[i + j + 2]:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
            continue
        if j % 2 or j < 2:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
print(count)

Python: h, n = map(int, input().split())
state_lst = [0] * h
for _ in range(n):
    x, y = map(int, input().split())
    state_lst[y] += 2 ** x

left_mask = 3
middle_mask = 6
right_mask = 12
all_mask = 15

INF = 10 ** 20
dp = [[-INF] * 2 ** 4 for _ in range(h + 1)]
dp[0][all_mask] = 0
for i in range(h):
    state = state_lst[i]
    for mask in (left_mask, middle_mask, right_mask):
        if (state & mask): continue
        for pre_state in range(16):
            if (pre_state & mask): continue
            dp[i + 1][state | mask] = max(dp[i + 1][state | mask], dp[i][pre_state] + 1)
    dp[i + 1][all_mask] = max(dp[i + 1][all_mask], -INF if state else (dp[i][0] + 2))
    dp[i + 1][state] = max(dp[i + 1][state], max(dp[i]))

print(max(dp[h]))

Python: h, n = map(int, input().split())
c = {i:set() for i in range(h)}
for i in range(n):
    a, b = map(int, input().split())
    c[b].add(a)
count = 0
for i in range(h - 1):
    l = c[i] | c[i + 1]
    p = None
    if l == set():
        count += 2
        c[i + 1].add(1)
        c[i + 1].add(2)
    elif 0 not in l and 1 not in l:
        p = 1
    elif 2 not in l and 3 not in l:
        p = 3
    elif 1 not in l and 2 not in l:
        p = 2
    if p:
        j = 0
        while i + j + 1 < h:
            if c[i + j + 1] == set():
                j += 1
            else:
                break
        if j % 2 or j < 2:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
print(count)

Python: import sys
sys.setrecursionlimit(10**6)
H, N = map(int, input().split())
P = [0]*H
for i in range(N):
    x, y = map(int, input().split())
    P[y] |= 1 << x

memo = [[-1]*16 for i in range(H)]
for i in range(16):
    memo[H-1][i] = 0
def dfs(i, state):
    if memo[i][state] != -1:
        return memo[i][state]
    p = P[i+1]
    s = state | p
    r = dfs(i+1, p)
    if s & 0b0011 == 0:
        r = max(r, dfs(i+1, p | 0b0011) + 1)
    if s & 0b0110 == 0:
        r = max(r, dfs(i+1, p | 0b0110) + 1)
    if s & 0b1100 == 0:
        r = max(r, dfs(i+1, p | 0b1100) + 1)
    if s & 0b1111 == 0:
        r = max(r, dfs(i+1, 0b1111) + 2)
    memo[i][state] = r
    return r
print(dfs(0, P[0]))

Python: h, n = map(int, input().split())
c = {i:set() for i in range(h + 1)}
for i in range(n):
    a, b = map(int, input().split())
    c[b].add(a)
c[h] = set([1, 2])
count = 0
for i in range(h - 1):
    l = c[i] | c[i + 1]
    p = None
    if l == set():
        count += 2
        c[i + 1].add(1)
        c[i + 1].add(2)
    elif 0 not in l and 1 not in l:
        p = 1
    elif 2 not in l and 3 not in l:
        p = 3
    elif 1 not in l and 2 not in l:
        p = 2
    if p:
        j = 0
        while i + j + 1 < h:
            if c[i + j + 1] == set():
                j += 1
            else:
                break
        if p != 2 and 3 - p not in c[i + j + 1] and 4 - p not in c[i + j + 1]:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
            continue
        if j % 2 or j < 2:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
print(count)

Python: import sys
sys.setrecursionlimit(10002)

H, N = [int(i) for i in input().split()]
locate_put = [set(), {0, 1}, {1, 2}, {2, 3}, {0, 1, 2, 3}]
not_jama = [{0, 1, 2, 3} for _ in range(H)]
known_fn = {}

for _ in range(N):
    xi, yi = [int(i) for i in input().split()]
    not_jama[yi].remove(xi)


def get_fn(h, way_put):
    if known_fn.get((h, way_put)):
        return known_fn[(h, way_put)]
    if h == 0:
        return 0
    best_count = 0
    for way, place_put in enumerate(locate_put):
        place_can_put = not_jama[h] - locate_put[way_put] & not_jama[h - 1]
        if place_put.issubset(place_can_put):
            count = get_fn(h - 1, way)
            count += 0 if way == 0 else 1 if way != 4 else 2
            best_count = count if count > best_count else best_count
    known_fn[(h, way_put)] = best_count
    return best_count


print(get_fn(H - 1, 0))