Problem E
Largest Hoarding

The real estate market in Metropolis is flourishing, and the main street in downtown Metropolis is now lined with a continuous row of high-rise buildings (skyscrapers). Not surprisingly, advertisers have been eager to put up large hoardings on the walls of these buildings. (For those unfamiliar with this use of “hoarding”, it is another word for “billboard” in many parts of the world.) After weighing the social and environmental impacts, the Metropolis city council decided to impose a ban on advertising hoardings along the main street. Following an intense legal battle, however, advertising agencies recently won a victory over the city’s hoardings ban when the high court declared the ban unconstitutional. The high court also recognized some of the merits of the ban, though, and ruled that hoardings may only be put up parallel to the main road, along the walls of the skyscrapers lining the road, and that hoardings must be rectangular in shape, and may not extend outside the skyline at any point.

As an account executive for a well-known advertising agency in Metropolis, you are excited by the high court’s decision. Recently, ABC Inc., a multinational retail corporation, hired your agency to design and install an advertisement hoarding for its new apparel business. In order to maximize its impact, ABC wants the size (surface area) of this hoarding to be as large as possible. You are handling ABC’s request, and hence you are busy calculating the largest possible billboard you can install, and therefore the largest amount of revenue your agency can collect from ABC each month. In Metropolis, the standard monthly cost of an advertisement hoarding is $\$ 50$ per square metre.

Figure 1: (a) An arrangement of skyscrapers, and (b) the largest hoarding (colored light red).

For example, suppose the Metropolis skyline appears as in Fig. 1(a), where the number at the top of each building specifies its height, and the number at the bottom of each building specifies its width (both quantities measured in metres). In this example, which corresponds to Sample Input 2, the largest legal hoarding (shown in Fig. 1(b)) spans the second, third, fourth, and fifth buildings, and has a height of $40$ metres, for a total surface area of $60 \cdot 40= 2\, 400$ square metres, so ABC will have to pay your agency $\$ 50 \cdot 2\, 400 = \$ 120\, 000$ per month.

Given an arrangement of skyscrapers, your task is to report the monthly advertising revenue for the largest legal advertisement hoarding.

Input

The first line of input contains an integer, $N$ ($1 \leq N \leq 10\, 000$), the number of skyscrapers. This is followed by $N$ lines describing the skyscrapers in left-to-right order. Each of these lines contains two space-separated integers, $H$ ($0 \leq H \leq 100$) and $W$ ($1 \leq W \leq 100$), specifying the height and width, respectively, of one skyscraper. The skyscrapers in the skyline are “tight”, i.e., there is no gap between adjacent buildings. Special case: the absence of a building in the skyline is indicated by a line with $H = 0$; this represents an empty lot whose width is given by the corresponding $W$ value.

Output

Output a line containing a single integer, the monthly advertising revenue for the largest legal hoarding that can be installed on the building skyline specified in the input.

9
1 1
2 1
3 1
4 1
5 1
4 1
3 1
2 1
1 1

750

7
20 10
50 20
40 10
60 10
40 20
30 10
20 10

120000