405307: GYM101879 D Maximizing Advertising

In Portugal there are very popular political parties, the Social Democrat Party (PSD, in Portuguese) and the Socialist Party (PS, in Portuguese). There will be presidential elections in Portugal in 2019 and the political parties are working on the best way to run advertising campaigns to reach the maximum number of voters.

Due to the high cost of elections advertising, PSD and PS wish to broker a deal and split the costs of advertising. The people in charge of the negotiation have data about political preference of some people in Portugal. They have been processing this information and have thus obtained the geographical position of people that are likely voters for PSD and PS. This position is represented by a point in the plane. To calculate the expenses, they wish to find two disjoint areas that, when summing likely voters for these parties, the result is the largest possible. To facilitate the computations, they decided to consider both areas to be rectangles with sides parallel to the axes. In other words, they wish to find two rectangles, one representing PSD and the other representing PS, such that the sum of the number of likely voters of PSD in the first rectangle and the number of the likely voters of PS in the second rectangle is maximum. You were hired to develop a software that fulfills this task.

The first line has an integer $$$N$$$, the number of people whose data will be considered. The next $$$N$$$ lines describe each person's data. The $$$i$$$th of these $$$N$$$ lines has two integers and a character, say $$$x_i$$$, $$$y_i$$$ and $$$p_i$$$. The integers represent a point $$$(x_i, y_i)$$$ and $$$p_i$$$ represents the political preference of the $$$i$$$th person.

Constraints

• $$$1 \leq N \leq 10^6$$$
• $$$-10^9 \leq x_i, y_i \leq 10^9$$$
• $$$p_i = $$$ "b" or $$$p_i = $$$ "w"

The maximum value that can be obtained when summing the number of likely voters in each rectangle. In this problem, we consider that points in the boundary are part of the rectangle.

3
0 0 b
0 1 b
1 1 b

3

4
0 0 b
1 1 w
2 2 b
3 3 w

3

4
-1 -1 b
0 0 b
1 1 w
2 2 w

4