Chessboard
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 65 Accepted Submission(s): 14
Problem Description
There are $N$ chess pieces on a huge chessboard of $10^9\times10^9$ ( the rows are numbered from $1$ to $10^9$ from top to bottom and the columns are numbered from $1$ to $10^9$ from left to right ) . All pieces are located in different grids , and the $i$-th piece is in the $y_i$-th column of the $x_i$-th row . All pieces have their own values , and the value of the $i$-th piece is exactly $i$ .
Your task is to take the chess pieces and maximize the sum of values of the pieces you take . But there are $M$ conditions of the following two types that should be met :
- " R $i$ $k$ " — there is a dividing line between the ($i-1$)-th row and the $i$-th row , and you can take up to $k$ from the pieces under the line ;
- " C $i$ $k$ " — there is a dividing line between the ($i-1$)-th column and the $i$-th column , and you can take up to $k$ from the pieces on the right of the line .
Your task is to take the chess pieces and maximize the sum of values of the pieces you take . But there are $M$ conditions of the following two types that should be met :
- " R $i$ $k$ " — there is a dividing line between the ($i-1$)-th row and the $i$-th row , and you can take up to $k$ from the pieces under the line ;
- " C $i$ $k$ " — there is a dividing line between the ($i-1$)-th column and the $i$-th column , and you can take up to $k$ from the pieces on the right of the line .
Input
The first line contains integer $N$ ( $1\leq N\leq500$ ) , denotes the number of chess pieces .
For the next $N$ lines , the $i$-th line contains two integers $x_i$ and $y_i$ , denotes the position of the $i$-th piece whose value is also $i$ .
The ($N+2$)-th line contains integer $M$ ( $1\leq M\leq10^5$ ) , denotes the number of conditions .
Then $M$ lines follow , describing conditions in the format given in the statement .
All input integers are between $1$ and $10^9$ .
For the next $N$ lines , the $i$-th line contains two integers $x_i$ and $y_i$ , denotes the position of the $i$-th piece whose value is also $i$ .
The ($N+2$)-th line contains integer $M$ ( $1\leq M\leq10^5$ ) , denotes the number of conditions .
Then $M$ lines follow , describing conditions in the format given in the statement .
All input integers are between $1$ and $10^9$ .
Output
Print the maximal sum of values of the chess pieces you take .
Sample Input
4 1 2 2 2 3 1 3 2 4 R 2 3 C 1 4 R 3 1 C 2 2
Sample Output
6
Hint
You can take the first three pieces ( or take the second piece and the fourth piece ) .
