Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Selling bamboo trees

    You have one bamboo tree. It grows at different speeds on different days. You’d like to earn some money by cutting and selling it (the tree still continue growing after you cut them).
    The bamboo has a length of 0 on day 1 and grows for n days. You’re aware of how much each meter of bamboo costs on each of the days and how much it grows the night before selling.
    notion image
    For each day you can either cut the whole tree (it still continues to grow after cutting) and sell it or you can leave it to grow further. What is the maximum amount of money you can earn?

    Input

    The first line of the input contains a single integer n (1 ≤ n ≤ ) the number of days.
    The next n lines contain two space-separated integers (, ) (1 ≤ , ) the number of meters the tree will grow the night before selling and the price for 1 meter of bamboo on the day i.

    Output

    The program should print the maximum amount you can earn by growing and selling the bamboo. It’s guaranteed that the answer does not exceed .

    Examples

    Input
    Output
    8 7 2 1 4 3 3 5 5 4 2 2 5 7 4 1 1
    139
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue