You are given n days and for each day (d_{i}) you can select one of the following options:
	perform no task 
	perform a high effort task (h_{i}) only if its the first day or if you chose no-task on the previous day
	perform a low effort task (l_{i})
Write a program to find the maximum amount of tasks you can perform within these n days. 
Example 1:
Input:
n = 3
hi[] = {2,8,1}
li[] = {1,2,1}
Output: 9
Explanation:
Options on 1st day: hi[0]=2, li[0]=1 or no-task
Select no-task.
Options on 2nd day: hi[1]=8, li[2]=1 or no-task
Select high-effort task as no-task was selected 
the previous day.  
Options on 3rd day: hi[2]=1, li[2]=1 or no-task
Select low-effort task as selecting high-effort 
task is only possible if you chose no-task on 
previous day.
Example 2:
Input:
n = 5
hi[] = {3,6,8,7,6}
li[] = {1,5,4,5,3}
Output: 20
Explanation: Perform high-effort task on first 
day and low-effort task on all remaining days.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxAmt() which accepts an integer n and two arrays li[] and hi[] as input parameter and returns the maximum amount of tasks you can perform within these n days.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 <= n <= 10^{6}

Difficulty: EASY
Tags: Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Starter code:
#User function Template for python3

class Solution:
    def maxAmt(self, n, hi, li): 
        # code here 


Solutions:
class Solution:

	def maxAmt(self, n, hi, li):
		dp = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			dp[i] = max(dp[i - 1], li[i - 1] + dp[i - 1], hi[i - 1] + (dp[i - 2] if i > 1 else 0))
		return dp[n]


class Solution:

	def maxAmt(self, n, hi, li):
		dp = [-1] * n

		def helper(n):
			if n < 0:
				return 0
			if dp[n] != -1:
				return dp[n]
			dp[n] = max(hi[n] + helper(n - 2), li[n] + helper(n - 1))
			return dp[n]
		return helper(n - 1)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def recursive_thinking(self, n, idx, hi, li, prev_skipped):
		if idx >= n:
			return 0
		if (idx, prev_skipped) in self.tb:
			return self.tb[idx, prev_skipped]
		if prev_skipped:
			choice1 = self.recursive_thinking(n, idx + 1, hi, li, True)
			choice2 = hi[idx] + self.recursive_thinking(n, idx + 1, hi, li, False)
			choice3 = li[idx] + self.recursive_thinking(n, idx + 1, hi, li, False)
			self.tb[idx, prev_skipped] = max(choice1, choice2, choice3)
		else:
			choice1 = self.recursive_thinking(n, idx + 1, hi, li, True)
			choice2 = li[idx] + self.recursive_thinking(n, idx + 1, hi, li, False)
			self.tb[idx, prev_skipped] = max(choice1, choice2)
		return self.tb[idx, prev_skipped]

	def maxAmt(self, n, hi, li):
		self.tb = {}
		return self.recursive_thinking(n, 0, hi, li, True)


class Solution:

	def maxAmt(self, n, hi, li):
		h = hi[0]
		no = 0
		l = li[0]
		for i in range(1, n):
			(h, no, l) = (hi[i] + no, max(h, l, no), li[i] + max(h, l, no))
		return max(h, l, no)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		hi = list(map(int, input().strip().split()))
		li = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxAmt(n, hi, li))


class Solution:

	def maxAmt(self, n, hi, li):
		dp = {}

		def solve(index):
			if index <= 0:
				return 0
			if index in dp:
				return dp[index]
			dp[index] = max(hi[index - 1] + solve(index - 2), li[index - 1] + solve(index - 1))
			return dp[index]
		return solve(n)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		hi = list(map(int, input().strip().split()))
		li = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxAmt(n, hi, li))


class Solution:

	def maxAmt(self, n, hi, li):

		def recur(ind, take):
			if ind >= len(hi):
				return 0
			(l1, h1, l2) = (0, 0, 0)
			if (ind, take) in cache:
				return cache[ind, take]
			if take:
				h1 = hi[ind] + recur(ind + 1, False)
			else:
				l1 = li[ind] + recur(ind + 1, False)
				l2 = recur(ind + 1, True)
			cache[ind, take] = max(l1, l2, h1)
			return max(l1, l2, h1)
		cache = {}
		return max(recur(0, True), recur(0, False))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		hi = list(map(int, input().strip().split()))
		li = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxAmt(n, hi, li))


class Solution:

	def maxAmt(self, n, h, l):
		hdp = [0] * n
		ldp = [0] * n
		fdp = [0] * n
		hdp[0] = h[0]
		ldp[0] = l[0]
		fdp[0] = h[0]
		for i in range(1, n):
			ldp[i] = fdp[i - 1] + l[i]
			if i - 1 == 0:
				hdp[i] = h[i]
			else:
				hdp[i] = fdp[i - 2] + h[i]
			fdp[i] = max(ldp[i], hdp[i])
		return fdp[-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		hi = list(map(int, input().strip().split()))
		li = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxAmt(n, hi, li))


class Solution:

	def maxAmt(self, n, hi, li):
		dp = []
		for i in range(n + 1):
			x = []
			for j in range(4):
				x.append(-1)
			dp.append(x)

		def solve(i, prev):
			if n == i:
				return 0
			if dp[i][prev] != -1:
				return dp[i][prev]
			res = 0
			if i == 0 or prev == 0:
				res = max(res, hi[i] + solve(i + 1, 2), 0 + solve(i + 1, 0))
			else:
				res = max(res, li[i] + solve(i + 1, 1), 0 + solve(i + 1, 0))
			dp[i][prev] = res
			return res
		return solve(0, 3)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		hi = list(map(int, input().strip().split()))
		li = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxAmt(n, hi, li))


class Solution:

	def recur(self, n, hi, li):
		global dp
		if n < 0:
			return 0
		if dp[n]:
			return dp[n]
		low = li[n] + self.recur(n - 1, hi, li)
		high = hi[n] + self.recur(n - 2, hi, li)
		dp[n] = max(low, high)
		return dp[n]

	def maxAmt(self, n, hi, li):
		if n == 1:
			return hi[0]
		dp = [0] * (n + 1)
		dp[1] = hi[0]
		for i in range(2, n + 1):
			dp[i] = max(li[i - 1] + dp[i - 1], hi[i - 1] + dp[i - 2])
		return dp[-1]


class Solution:

	def recur(self, n, hi, li):
		global dp
		if n < 0:
			return 0
		if dp[n]:
			return dp[n]
		low = li[n] + self.recur(n - 1, hi, li)
		high = hi[n] + self.recur(n - 2, hi, li)
		dp[n] = max(low, high)
		return dp[n]

	def maxAmt(self, n, hi, li):
		global dp
		dp = [0] * n
		return self.recur(n - 1, hi, li)
		print(dp)


class Solution:

	def maxAmt(self, n, hi, li):
		memo = {}

		def helper(indx):
			if indx in memo:
				return memo[indx]
			if indx <= 0:
				return 0
			high = hi[indx - 1] + helper(indx - 2)
			low = li[indx - 1] + helper(indx - 1)
			memo[indx] = max(high, low)
			return memo[indx]
		return helper(n)


class Solution:

	def maxAmt(self, n, hi, li):
		dp = [0] * (n + 1)
		dp[0] = 0
		dp[1] = hi[0]
		for i in range(2, n + 1):
			dp[i] = max(hi[i - 1] + dp[i - 2], li[i - 1] + dp[i - 1])
		return dp[n]

		def helper(indx):
			if indx > n:
				return 0
			if indx == n:
				return 0
			if indx == 1:
				return hi[indx]
			high = hi[indx] + helper(indx + 2)
			low = li[indx] + helper(indx + 1)
			return max(high, low)
		return helper(0)


class Solution:

	def maxAmt(self, n, hi, li):
		if n == 1:
			return max(hi[0], li[0])
		h = [0 for i in range(n)]
		l = [0 for i in range(n)]
		no = [0 for i in range(n)]
		h[0] = hi[0]
		l[0] = li[0]
		no[0] = 0
		for i in range(1, n):
			h[i] = no[i - 1] + hi[i]
			l[i] = max(l[i - 1], h[i - 1], no[i - 1]) + li[i]
			no[i] = max(l[i - 1], h[i - 1], no[i - 1])
		return max(h[n - 1], l[n - 1], no[n - 1])


class Solution:

	def maxAmt(self, n, hi, li):
		a = hi[0]
		b = 0
		for i in range(1, n):
			t = a
			a = max(a + li[i], hi[i] + b)
			b = t
		return a


class Solution:

	def maxAmt(self, n, hi, li):
		d = [[-1 for _ in range(n)] for __ in range(3)]
		return self.get(n, hi, li, 0, 0, d)

	def get(self, n, hi, li, i, prv, d):
		if i >= n:
			return 0
		elif d[prv][i] != -1:
			return d[prv][i]
		elif prv == 0:
			d[prv][i] = max(self.get(n, hi, li, i + 1, 0, d), li[i] + self.get(n, hi, li, i + 1, 1, d), hi[i] + self.get(n, hi, li, i + 1, 2, d))
		else:
			d[prv][i] = max(self.get(n, hi, li, i + 1, 0, d), li[i] + self.get(n, hi, li, i + 1, 1, d))
		return d[prv][i]


class Solution:

	def maxAmt(self, n, hi, li):
		soln = [0 for i in range(n + 1)]
		if n <= 0:
			return 'Zero, cause no Solution Exists!'
		if n == 1:
			return max(hi[0], li[0])
		soln[0] = 0
		soln[1] = hi[0]
		for i in range(2, n + 1):
			soln[i] = max(hi[i - 1] + soln[i - 2], li[i - 1] + soln[i - 1])
		return soln[n]


class Solution:

	def maxAmt(self, n, high, low):
		dp = [0] * (n + 1)
		dp[1] = high[0]
		for i in range(2, n + 1):
			dp[i] = max(high[i - 1] + dp[i - 2], low[i - 1] + dp[i - 1])
		return dp[n]


class Solution:

	def maxAmt(self, n, hi, li):
		arr = [0, hi[0]]
		for x in range(1, len(hi)):
			arr.append(max(arr[-2] + hi[x], arr[-1] + li[x], arr[-1]))
		return arr[-1]