Splitting a Histogram into Rectangles

Jaewoo received a histogram as a gift from Jaehyeon. A histogram is a figure made of several rectangles aligned along the bottom. The width and height of each rectangle may differ. For example, the following figure is a histogram with rectangles of size $\left( 5,4 \right)$, $\left( 2,8 \right)$, and $\left( 1,5 \right)$ placed side by side.

Jaewoo found the uneven histogram hard to store, so he wants to cut it into pieces that are rectangles. Each cut costs effort equal to the length of the cut. Jaewoo is not strong, so he wants to split the histogram with the least effort.

For example, if the histogram above is cut as in the left figure below, the cost is $9$. If it is cut as in the right figure, the cost is $4$, which is the minimum.

Given the histogram Jaewoo received from Jaehyeon, find the minimum effort needed to cut it into rectangles.

The first line contains the number of rectangles that make up the histogram, $N(1\leq N\leq 500)$.

From the second line through the $N$th line, each line contains two integers $X\_i,Y\_i(1\leq X\_i,Y\_i\leq 10^9)$, the width and height of each rectangle. The rectangles are given separated by a space, in order from left to right.

Print the minimum effort needed to cut the given histogram into rectangles on the first line.