You have 2 counters a and b, both initialised as 0. You also have a score initialised as 0.

At the start of every minute from minute 1 to minute N, you must increase either a or b by 1.

Additionally, there are M events. The i^{th} event happens at minute T_{i}+0.5 and has type C_{i} (C_{i} \in \{1, 2\}).

At each event, the counters or the score is updated as:

if (type == 1):
if (a > b):
score = score + 1;
else:
a = 0;
b = 0;
else:
if (a < b):
score = score + 1;
else:
a = 0;
b = 0;

Your task is to maximise the score after N minutes have passed.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and M — the number of minutes and the number of events.
- The second line of each test case contains M integers T_{1},T_{2},\ldots,T_{M} — where the i^{th} event happens at minute T_{i} + 0.5.
- The third line of each test case contains M integers C_{1},C_{2},\ldots,C_{M} — the type of the i^{th} event.

------ Output Format ------ 

For each test case, output on a new line, the maximum score after N minutes have passed.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ M ≤ N ≤ 10^{5}$
$1 ≤ T_{1} < T_{2} < \ldots < T_{M} ≤ N$
$C_{i} \in \{1,2\}$
- The sum of $N$ over all test cases will not exceed $10^{5}$.

----- Sample Input 1 ------ 
4
5 3
1 2 5
1 2 1
5 5
1 2 3 4 5
1 1 1 1 1
5 5
1 2 3 4 5
1 2 1 2 1
1 1
1
2

----- Sample Output 1 ------ 
2
5
3
1

----- explanation 1 ------ 
Test case $1$: We will demonstrate a way to achieve a score of $2$.

- In the first minute, we will increase $a$ by $1$ so that $a=1$ and $b=0$. Since there is an event with type $1$ and $a> b$ our score increases by $1$.
- In the second minute, we will increase $b$ by $1$ so that $a=1$ and $b=1$. Since there is an event with type $2$ and $a$ is not less than $b$, our score remains $1$ and the counters are reset.
- In the third minute, we will increase $a$ by $1$ so that $a=1$ and $b=0$. There are no events in this minute. 
- In the fourth minute, we will increase $a$ by $1$ so that $a=2$ and $b=0$. There are no events in this minute.
- In the fifth minute, we will increase $a$ by $1$ so that $a=3$ and $b=0$. Since there is an event with type $1$ and $a> b$ our score increases by $1$.

Thus, the total score achieved is $2$.  
It can be shown that there is no possible way for our score to be greater than $2$.

Test case $2$: We will demonstrate a way to achieve a score of $5$.

- In the first minute, we will increase $a$ by $1$ so that $a=1$ and $b=0$. Since there is an event with type $1$ and $a> b$ our score increases by $1$.
- In the second minute, we will increase $a$ by $1$ so that $a=2$ and $b=0$. Since there is an event with type $1$ and $a> b$ our score increases by $1$.
- In the third minute, we will increase $a$ by $1$ so that $a=3$ and $b=0$. Since there is an event with type $1$ and $a> b$ our score increases by $1$.
- In the fourth minute, we will increase $a$ by $1$ so that $a=4$ and $b=0$. Since there is an event with type $1$ and $a> b$ our score increases by $1$.
- In the fifth minute, we will increase $a$ by $1$ so that $a=5$ and $b=0$. Since there is an event with type $1$ and $a> b$ our score increases by $1$.

Thus, the total score achieved is $5$.  
It can be shown that there is no possible way for our score to be greater than $5$.

Difficulty: VERY_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from collections import Counter
for t in range(int(input())):
	(NN, MM) = map(int, input().split(' '))
	Ts = list(map(int, input().split(' ')))
	Cs = list(map(int, input().split(' ')))
	inc = 0
	next_c = [Ts[inc], Cs[inc]]
	master = Counter({0: 0})
	for it in range(1, NN + 1):
		new_master = Counter()
		for m in master:
			new_master[m + 1] = max(new_master[m + 1], master[m])
			new_master[m - 1] = max(new_master[m - 1], master[m])
		master = {i: new_master[i] for i in new_master if abs(i) <= 5}
		if next_c[0] == it:
			new_master = Counter()
			for m in master:
				if next_c[1] == 1:
					if m > 0:
						new_master[m] = max(new_master[m], master[m] + 1)
					else:
						new_master[0] = max(new_master[0], master[m])
				elif m < 0:
					new_master[m] = max(new_master[m], master[m] + 1)
				else:
					new_master[0] = max(new_master[0], master[m])
			master = new_master
			inc += 1
			if inc < MM:
				next_c = [Ts[inc], Cs[inc]]
	lst = [master[i] for i in master]
	print(max(lst))


for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	n = n + 1
	t = [int(i) for i in input().split()]
	c = [int(i) for i in input().split()]
	C = {}
	for i in range(m):
		C[t[i] + 1] = c[i]
	dp = [[-1000000000.0 for i in range(5)] for j in range(n + 1)]
	dp[0][2] = 0
	for i in range(1, n + 1):
		if i in C:
			if C[i] == 1:
				dp[i][0] = -1000000000.0
				dp[i][1] = max(dp[i - 1][2], dp[i - 1][1], dp[i - 1][0])
				dp[i][2] = dp[i - 1][3] + 1
				dp[i][3] = max(dp[i - 1][2], dp[i - 1][1], dp[i - 1][0], dp[i - 1][4] + 1)
				dp[i][4] = dp[i - 1][3] + 1
			else:
				dp[i][4] = -1000000000.0
				dp[i][3] = max(dp[i - 1][2], dp[i - 1][3], dp[i - 1][4])
				dp[i][2] = dp[i - 1][1] + 1
				dp[i][1] = max(dp[i - 1][2], dp[i - 1][3], dp[i - 1][4], dp[i - 1][0] + 1)
				dp[i][0] = dp[i - 1][1] + 1
		else:
			for j in range(5):
				lst = []
				if j - 1 >= 0:
					lst.append(dp[i - 1][j - 1])
				if j + 1 <= 4:
					lst.append(dp[i - 1][j + 1])
				dp[i][j] = max(lst)
	print(max(dp[n]))


inf = 10 ** 9
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	times = list(map(int, input().split()))
	types = list(map(int, input().split()))
	dp = [[-inf, -inf, -inf, -inf, -inf] for _ in range(n + 2)]
	dp[0][2] = 0
	ptr = 0
	for i in range(1, n + 1):
		for dif in range(5):
			if dif > 0:
				dp[i][dif] = max(dp[i][dif], dp[i - 1][dif - 1])
			if dif < 4:
				dp[i][dif] = max(dp[i][dif], dp[i - 1][dif + 1])
		if ptr < m and times[ptr] == i:
			if types[ptr] == 1:
				dp[i][4] += 1
				dp[i][3] += 1
				dp[i][2] = max(dp[i][:3])
				dp[i][0] = -inf
				dp[i][1] = -inf
			else:
				dp[i][0] += 1
				dp[i][1] += 1
				dp[i][2] = max(dp[i][2:])
				dp[i][3] = -inf
				dp[i][4] = -inf
			ptr += 1
	print(max(dp[n]))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	t = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = [[-3, -3, -3, -3, -3] for i in range(n + 1)]
	d[0][2] = 0
	idx = 0
	for i in range(1, n + 1):
		d[i][0] = max(d[i][0], d[i - 1][1])
		d[i][1] = max(d[i][1], d[i - 1][0], d[i - 1][2])
		d[i][2] = max(d[i - 1][1], d[i][2], d[i - 1][3])
		d[i][3] = max(d[i - 1][2], d[i - 1][4], d[i][3])
		d[i][4] = max(d[i][4], d[i - 1][3])
		if idx < m and t[idx] == i:
			if c[idx] == 1:
				d[i][4] += 1
				d[i][3] += 1
				d[i][2] = max(d[i][2], d[i][1], d[i][0])
				d[i][1] = -3
				d[i][0] = -3
			else:
				d[i][0] += 1
				d[i][1] += 1
				d[i][2] = max(d[i][2], d[i][3], d[i][4])
				d[i][3] = -3
				d[i][4] = -3
			idx += 1
	print(max(d[n][0], d[n][1], d[n][2], d[n][3], d[n][4]))


TT = int(input())
for tt in range(TT):
	(n, m) = map(int, input().split())
	T = map(int, input().split())
	C = map(int, input().split())
	state = [0, -100, -100]
	(prev_t, prev_c) = (0, 0)
	for (t, c) in zip(T, C):
		diff = t - prev_t
		new_state = [-100, -100, -100]
		if c == prev_c:
			if diff % 2 == 0:
				v = max(state[0], state[1], state[2])
			else:
				v = max(state[0], state[1])
				if diff > 1:
					v = max(v, state[2])
		else:
			v = max(state[0], state[1], state[2])
		new_state[0] = max(new_state[0], v)
		if c == prev_c:
			if diff % 2 == 0:
				new_state[1] = max(state[1] + 1, new_state[1])
			else:
				new_state[1] = max(state[0] + 1, state[2] + 1, new_state[1])
		elif diff % 2 == 0:
			new_state[1] = max(state[1] + 1, new_state[1])
		else:
			new_state[1] = max(state[0] + 1, new_state[1])
			if diff > 1:
				new_state[1] = max(state[2] + 1, new_state[1])
		if c == prev_c:
			if diff % 2 == 0:
				new_state[2] = max(state[0] + 1, state[2] + 1, new_state[2])
			else:
				new_state[2] = max(state[1] + 1, new_state[2])
		elif diff % 2 == 0:
			new_state[2] = max(state[0] + 1, new_state[2])
			if diff > 2:
				new_state[2] = max(state[2] + 1, new_state[2])
		elif diff > 1:
			new_state[2] = max(state[1] + 1, new_state[2])
		prev_t = t
		prev_c = c
		state = new_state
	print(max(state))