## Wesley's Anger Contest 2 Problem 2 - Costume Shopping

View as PDF

Points: 10
Time limit: 1.0s
Java 2.5s
Python 2.5s
Memory limit: 256M

Author:
Problem type

With Halloween coming up in days, you realized that you need to buy costumes! Specifically, you want to buy different costumes before Halloween so that you have multiple options to choose from on Halloween. Thankfully there is a store nearby that allows you to buy at most one costume a day, however the price of the costume keeps changing. Initially, the costumes will cost , however over the course of days, they will change different times. You will be given this list of changes beforehand which will tell you that at some moment on the day before Halloween, the price of buying a costume changes to . The list will be in the order that the changes occurred. Can you determine the minimum cost to buy all costumes?

Note that the price of a costume may change multiple times during a given day, and you can choose what time you will enter the store to buy the costume. In addition, the store will open the next day with the costumes having the exact price that it closed at the previous day (a price change will not happen overnight, nor at the moment the store opens or closes).

for
for
for

#### Input Specification

The first line of input contains integers, .

The next lines describe the changes in the price of a costume, listed in the order that the changes occurred. Each line contains integers, . This indicates that on the day before Halloween, the price of buying a costume changes to .

Note that a 64-bit integer may need to be used to store and . In C++, this can be done with long long. In Java, this can be done with long. In Python, the standard int will suffice.

#### Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single integer, the minimum cost to buy costumes, before Halloween, given that you can buy at most one costume a day. Note that this answer may not necessarily fit in a 32-bit integer.

#### Sample Input

7 3 6
6 10
4 1
3 5
2 8
2 2
2 7

#### Sample Output

4

#### Sample Explanation

You can buy a costume days before Halloween right after the price changes to . You can then buy a costume days before Halloween for right when the store opens, and buy a costume days before Halloween right after the price changes to .