Under construction

Still being built. Things may change

Bitcoin Bubble

Interview

Time limit2sMemory limit2048 MB

Summary
Given price segments of consecutive days, find the maximum of the longest window around a day x where no price drops below the price on x, times that price.
Level

Medium5 of 10

Topics
Stack, Prefix sum, Array
Solved
No attempts yet

Problem

These days, all eyes and money are on crypto. The stakes are high, and a team of experts who call themselves the FPC (Fabulous People of Crypto) is on the verge of a big move. They call their move "The Bubble".

The Bubble works as follows. One day, the FPC will release a set of classified information that will shake the market to its roots. That day, call it xx, is the epicenter of their move. To measure the impact of The Bubble, consider the longest sequence of consecutive days, starting on day aa and ending on day bb (a≤x≤ba\leq x\leq b), for which Bitcoin's price is never lower than its price on day xx. The impact is the length of this sequence in days multiplied by the price of Bitcoin on day xx. The starting day and the ending day must lie within the period for which the FPC know the price.

The FPC can predict prices but cannot program. Help them find the biggest possible impact of The Bubble, given that they release the information on an optimal day.

Input

The first line contains a single integer nn (1≤n≤5⋅1041\leq n\leq 5\cdot 10^4), the number of price predictions for Bitcoin.

Each of the next nn lines contains two integers pp and dd (0≤p≤2⋅1090\leq p\leq 2\cdot 10^9 and 1≤d≤5⋅1041\leq d\leq 5\cdot 10^4). The price is pp and it lasts for dd days. The price information is given in chronological order.

Output

Output a single number, the biggest impact The Bubble can have.

Examples2

  1. Example 1

    Input
    4
    3 2
    9 4
    5 2
    7 4
    
    Expected output
    50
    
  2. Example 2

    Input
    10
    5 5
    8 1
    8 3
    9 1
    0 6
    1 6
    1 5
    6 2
    6 5
    9 6
    
    Expected output
    78