You are given an N × N grid initially filled by zeros. Let the rows and columns of the grid be numbered from1 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

原题：

http://www.codechef.com/problems/ROWCOLOP

很好的题目，巧妙地计算最终结果。

注意： 

1 行列分开计算，最后组合最大值就是答案了， 不用搜索二维表

2 只需要记录行列的最终结果就可以，不用模拟全过程

3 数据量非常大，处理输入问题

下面程序0ms通过，全网站本题最好答案，呵呵。

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

class RowAndColumnOperations
{
	static const int MAX_BU = 5120;
	int st, len;
	char buffer[MAX_BU];

	char getFromBuffer()
	{
		if (st >= len)//st <= len??? Really? more careful!!!
		{
			len = fread(buffer, 1, MAX_BU, stdin);//forget len=???
			st = 0;
		}
		return buffer[st++];
	}
	
	char getCharFromBuf()
	{
		char c = getFromBuffer();
		while (len)
		{
			if (‘a‘ <= c && c <= ‘z‘ || ‘A‘ <= c && c <= ‘Z‘) return c;
			c = getFromBuffer();
		}
		return ‘0‘;
	}

	int getInt()
	{
		char c = getFromBuffer();
		while ((c < ‘0‘ || ‘9‘ < c) && len)
		{
			c = getFromBuffer();
		}
		int num = 0;
		while (‘0‘ <= c && c <= ‘9‘ && len)
		{
			num = (num<<3) + (num<<1) + (c - ‘0‘);
			c = getFromBuffer();
		}
		return num;
	}

public:
	RowAndColumnOperations() : st(0), len(0)
	{
		int N, Q, RC, addNum, MaxC = 0, MaxR = 0;
		N = getInt()+1;
		int *rows = (int *) malloc(sizeof(int) * N);
		int *cols = (int *) malloc(sizeof(int) * N);
		memset(rows, 0, sizeof(int) * N);
		memset(cols, 0, sizeof(int) * N);

		Q = getInt();
		char Commands[7];
		while (Q--)
		{			
			for (int i = 0; i < 6; i++)
			{
				Commands[i] = getCharFromBuf();
			}
			RC = getInt();
			addNum = getInt();
			if (Commands[0] == ‘R‘)
			{
				rows[RC] += addNum;
				MaxC = MaxC < rows[RC] ? rows[RC] : MaxC;
			}
			else
			{
				cols[RC] += addNum;
				MaxR = MaxR < cols[RC] ? cols[RC] : MaxR;
			}
		}
		printf("%d", MaxC + MaxR);
		free(rows);
		free(cols);
	}
};

int rowAndColumnOperations()
{
	RowAndColumnOperations();
	return 0;
}