히스토그램 직사각형으로 쪼개기

재우는 재현이에게 히스토그램을 선물로 받았다. 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 이때 각 직사각형의 가로 길이와 세로 길이는 서로 다를 수 있다. 예를 들어 다음 그림은 가로 길이와 세로 길이가 각각 $\left( 5,4 \right)$, $\left( 2,8 \right)$, $\left( 1,5 \right)$인 직사각형들이 붙어 있는 히스토그램이다.

울퉁불퉁한 모양의 히스토그램은 보관하기 힘들어서, 재우는 히스토그램을 적당히 잘라 직사각형 모양으로 보관하려고 한다. 재우가 히스토그램을 자르면 자른 길이만큼 힘이 든다. 힘이 세지 않은 재우는 최소한의 힘으로 히스토그램을 나누고자 한다.

예를 들어 위의 히스토그램을 아래 왼쪽 그림처럼 자르면 $9$의 힘이 들고, 오른쪽 그림처럼 자르면 $4$의 힘이 드는데, 이 값이 최소이다.

재우가 재현이에게 받은 히스토그램의 정보가 주어질 때, 이 히스토그램을 직사각형 모양으로 자르는 데 필요한 힘의 최솟값을 구해보자.

첫 번째 줄에 히스토그램을 이루는 직사각형의 개수 $N(1\leq N\leq 500)$이 주어진다.

두 번째 줄부터 $N$줄에 걸쳐 히스토그램을 이루는 직사각형의 가로 길이와 세로 길이를 나타내는 두 정수 $X\_i,Y\_i(1\leq X\_i,Y\_i\leq 10^9)$가 공백으로 구분되어, 왼쪽부터 이어진 순서대로 주어진다.

첫 번째 줄에 주어진 히스토그램을 직사각형 모양으로 자르는 데 필요한 힘의 최솟값을 출력한다.