러시아 인형

러시아 기념품 인형은 큰 인형 속에 더 작은 인형이 들어 있는 나무 인형이다. 인형을 전부 분리해서 하나씩 살펴보자. $i$번 인형의 겉부피 $out_i$는 그 인형이 공간에서 차지하는 부피이고, 속부피 $in_i$는 인형 안쪽 빈 공간의 부피이다. 한 인형의 겉부피가 다른 인형의 속부피보다 엄격하게 작으면 앞의 인형을 뒤의 인형 안에 넣을 수 있다. 한 인형 안에 인형을 두 개 이상 넣을 때는 나란히 둘 수 없고, 겹겹이 포개어 넣어야 한다.

인형마다 안에 남은 빈 공간의 값을 치른다. $i$번 인형에 직접 속하는 빈 공간, 즉 $i$번 인형 안쪽에서 바로 안에 넣은 인형이 차지하지 않은 부분은 한 단위마다 $cost_i$를 낸다. 안에 아무것도 넣지 않은 인형은 속부피 전체가 빈 공간이다. 규칙만 지키면 인형을 원하는 대로 넣을 수 있고, 전부 넣지 않아도 된다. 치러야 하는 비용의 합이 가장 작아지도록 인형을 넣고, 그 비용을 구하시오.

첫째 줄에 인형의 개수 $N$ ($1 \le N \le 1000$)이 주어진다. 다음 $N$개 줄 중 $i$번째 줄에는 $i$번 인형의 겉부피 $out_i$, 속부피 $in_i$, 빈 공간 한 단위당 비용 $cost_i$가 공백으로 구분되어 주어진다 ($1 \le in_i < out_i \le 1000$, $1 \le cost_i \le 1000$).

치러야 하는 비용의 최솟값 $P$를 정수 하나로 출력한다.