#include <bits/stdc++.h>

using namespace std;
vector< vector<int> > mat;
const int INF = 1e6;
int nwa(string a, string b , int i , int j){
	if(mat[i][j] != -INF) 
		return mat[i][j];
	else{
		int val1;
		if(i > 0 && j > 0 && a[i - 1] == b[j - 1])
			val1 = nwa(a , b, i - 1, j - 1) + 1; 
		else
			val1 = nwa(a , b, i - 1, j - 1) - 1;
		int val2 = nwa(a , b, i - 1, j) - 2;
		int val3 = nwa(a , b, i, j - 1) - 2;
		return mat[i][j] = max({val1 , val2 , val3});
	}
}


signed main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(NULL);
	string a = "AAAC";
	string b = "AGC";
	int m = a.size();
	int n = b.size();
	mat.assign(m + 1, vector<int>(n + 1, -INF));
	int cnt = 0;
	for(int i = 0 ; i <= n; i++) mat[0][i] = cnt, cnt -= 2; 
	cnt = 0;
	for(int i = 0 ; i <= m; i++) mat[i][0] = cnt, cnt -= 2;
	int ans = nwa(a , b,  m , n);
	for(auto v : mat){
		for(int i : v)
			cout << i << "\t\t";
		cout << endl;
	}
	cout << "RES:\n";
	cout << ans << endl;
	return 0;
}