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

문제

재우는 재현이에게 히스토그램을 선물로 받았다. 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 이 때, 각 직사각형의 가로 길이와 세로 길이는 서로 다를 수도 있다. 예를 들어, 다음 그림은 가로 길이와 세로 길이가 각각 $\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)$가 공백으로 구분되어 왼쪽부터 이어진 순서대로 주어진다.

출력

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

제한

힌트