You are given an N × N grid initially filled by zeros. Let the rows and columns of the grid be numbered from 1 to N, inclusive. There are two types of operations can be applied to the grid:

- RowAdd R X: all numbers in the row R should be increased by X.
- ColAdd C X: all numbers in the column C should be increased by X.

Now after performing the sequence of such operations you need to find the maximum element in the grid.

-----Input-----
The first line of the input contains two space separated integers N and Q denoting the size of the grid and the number of performed operations respectively. Each of the following Q lines describe an operation in the format described above.

-----Output-----
Output a single line containing the maximum number at the grid after performing all the operations.

-----Constraints-----
- 1 ≤ N ≤ 314159
- 1 ≤ Q ≤ 314159
- 1 ≤ X ≤ 3141
- 1 ≤ R, C ≤ N

-----Example-----
Input:
2 4
RowAdd 1 3
ColAdd 2 1
ColAdd 1 4
RowAdd 2 1

Output:
7

-----Explanation-----
The grid changes as follows:
00  33  34  74  74
00  00  01  41  52

The maximum number in the final grid is 7.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(n, q) = map(int, input().split())
dr = {}
dc = {}
for i in range(1, n + 1):
	dr[i] = 0
	dc[i] = 0
mer = 0
mec = 0
for i in range(q):
	(s, j, k) = input().split()
	j = int(j)
	k = int(k)
	if s == 'RowAdd':
		dr[j] += k
		if dr[j] > mer:
			mer = dr[j]
	else:
		dc[j] += k
		if mec < dc[j]:
			mec = dc[j]
print(mer + mec)


(N, Q) = [int(i) for i in input().split()]
row = [0 for i in range(N)]
col = [0 for i in range(N)]
for i in range(Q):
	x = input().split()
	if x[0] == 'RowAdd':
		row[int(x[1]) - 1] += int(x[2])
	else:
		col[int(x[1]) - 1] += int(x[2])
print(max(row) + max(col))


(n, q) = list(map(int, input().split()))
row = [0] * n
column = [0] * n
for i in range(q):
	(a, b, c) = input().split()
	if a == 'RowAdd':
		row[int(b) - 1] += int(c)
	else:
		column[int(b) - 1] += int(c)
print(max(row) + max(column))


from sys import stdin, stdout
(n, q) = [int(x) for x in stdin.readline().split()]
row = [0] * n
col = [0] * n
for i in range(q):
	(a, b, c) = input().split()
	if a == 'RowAdd':
		row[int(b) - 1] += int(c)
	else:
		col[int(b) - 1] += int(c)
print(max(row) + max(col))


from sys import stdin, stdout
from math import gcd, log2, log10, floor
import math
from collections import defaultdict, OrderedDict
from bisect import bisect_left
(n, q) = list(map(int, input().split()))
r = [0] * (n + 1)
c = [0] * (n + 1)
for i in range(q):
	(alpha, beta, gamma) = list(map(str, input().split()))
	(beta, gamma) = (int(beta), int(gamma))
	if alpha == 'RowAdd':
		r[beta] += gamma
	else:
		c[beta] += gamma
print(max(r) + max(c))


for u in range(1):
	(n, q) = list(map(int, input().split()))
	(l, d) = ([0] * n, [0] * n)
	for i in range(q):
		s = input().split()
		if s[0] == 'RowAdd':
			(x, y) = (int(s[1]), int(s[2]))
			l[x - 1] += y
		else:
			(x, y) = (int(s[1]), int(s[2]))
			d[x - 1] += y
	print(max(l) + max(d))


(n, operations) = map(int, input().split())
rows = [0] * n
columns = [0] * n
maxi = -float('Inf')
for i in range(operations):
	temp = input().split()
	if temp[0] == 'RowAdd':
		rows[int(temp[1]) - 1] += int(temp[2])
	else:
		columns[int(temp[1]) - 1] += int(temp[2])
print(max(rows) + max(columns))


import sys
import os
import math
import copy
from bisect import bisect
from io import BytesIO, IOBase
from collections import deque, Counter, defaultdict
from itertools import permutations, combinations

def Int():
	return int(sys.stdin.readline())

def Mint():
	return map(int, sys.stdin.readline().split())

def Lstr():
	return list(sys.stdin.readline().strip())

def Str():
	return sys.stdin.readline().strip()

def Mstr():
	return map(str, sys.stdin.readline().strip().split())

def List():
	return list(map(int, sys.stdin.readline().split()))

def Hash():
	return dict()

def Mod():
	return 1000000007

def Ncr(n, r, p):
	return fact[n] * (ifact[r] * ifact[n - r] % p) % p

def Most_frequent(list):
	return max(set(list), key=list.count)

def Mat2x2(n):
	return [List() for _ in range(n)]

def solution():
	(n, k) = map(int, input().split())
	m = -float('inf')
	a = [0 for i in range(n)]
	b = [0 for i in range(n)]
	for i in range(k):
		(q, r, e) = map(str, input().split())
		(r, e) = (int(r), int(e))
		if q[0] == 'R':
			a[r - 1] += e
		else:
			b[r - 1] += e
	print(str(max(a) + max(b)) + '\n')

def __starting_point():
	solution()
__starting_point()


(n, q) = list(map(int, input().split()))
r = [0] * n
c = [0] * n
for _ in range(q):
	(s, x, p) = list(map(str, input().split()))
	(x, p) = (int(x), int(p))
	if s == 'RowAdd':
		r[x - 1] += p
	else:
		c[x - 1] += p
print(max(r) + max(c))


(n, q) = map(int, input().split())
a = [0] * n
b = [0] * n
while q > 0:
	(o, r, v) = input().split()
	if o == 'RowAdd':
		a[int(r) - 1] += int(v)
	else:
		b[int(r) - 1] += int(v)
	q = q - 1
print(max(a) + max(b))


(n, q) = map(int, input().split())
g = [0] * n
g1 = [0] * n
while q > 0:
	(o, r, v) = input().split()
	if o == 'RowAdd':
		g[int(r) - 1] += int(v)
	else:
		g1[int(r) - 1] += int(v)
	q = q - 1
print(max(g) + max(g1))


(n, k) = list(map(int, input().strip().split()))
m1 = dict()
m2 = dict()
for _ in range(k):
	list1 = input().split()
	a = list1[0]
	b = int(list1[1])
	c = int(list1[2])
	if a == 'RowAdd':
		if b in m1:
			m1[b] += c
		else:
			m1[b] = c
	elif b in m2:
		m2[b] += c
	else:
		m2[b] = c
max1 = 0
for val in m1:
	if m1[val] > max1:
		max1 = m1[val]
max2 = 0
for val in m2:
	if m2[val] > max2:
		max2 = m2[val]
print(max1 + max2)


import operator
(n, q) = map(int, input().split())
x = [0] * (n + 1)
y = [0] * (n + 1)
for _ in range(q):
	a = input().split()
	if a[0] == 'RowAdd':
		x[int(a[1])] += int(a[2])
	else:
		y[int(a[1])] += int(a[2])
print(max(x) + max(y))


(n, m) = list(map(int, input().split()))
a = [0] * (n + 1)
b = [0] * (n + 1)
for i in range(0, m):
	op = input().split()
	if op[0] == 'RowAdd':
		a[int(op[1])] += int(op[2])
	if op[0] == 'ColAdd':
		b[int(op[1])] += int(op[2])
print(max(a) + max(b))


check_digit = lambda x: int(x) if x.isdigit() else x
(n, q) = map(int, input().split())
rows = {i: 0 for i in range(n)}
columns = {i: 0 for i in range(n)}
for _ in range(q):
	(op, num, x) = map(check_digit, input().split())
	if op == 'RowAdd':
		rows[num - 1] += x
	else:
		columns[num - 1] += x
print(max(rows.values()) + max(columns.values()))


(n, q) = map(int, input().split())
row = [0] * n
col = [0] * n
for i in range(q):
	s = input()
	if s[0] == 'R':
		(r, x) = map(int, s.split()[1:])
		row[r - 1] += x
	else:
		(c, x) = map(int, s.split()[1:])
		col[c - 1] += x
print(max(row) + max(col))


(N, T) = map(int, input().split())
r = [0] * (N + 1)
c = [0] * (N + 1)
for i in range(T):
	task = input().split()
	if task[0] == 'RowAdd':
		r[int(task[1])] += int(task[2])
	if task[0] == 'ColAdd':
		c[int(task[1])] += int(task[2])
print(max(r) + max(c))