Hi everyone. Today i meet a problem like that: There are n cities, and each city i has a height h_i and a rental cost p_i for using a flying vehicle. To travel from city i to city j, the cost is defined as: cost(i, j) = max(p_i, h_j — h_i).

A tourist wants to start from city 1, visit all cities exactly once, and finally return to city 1, using the flying vehicle. Your task is to determine the minimum total travel cost.

Input: • The first line contains an integer n (1 ≤ n ≤ 10⁵) — the number of cities. • Each of the next n lines contains two integers h_i and p_i (0 ≤ h_i, p_i ≤ 10⁹) — the height and the rental cost of city i.

Output: • Output a single integer — the minimum total cost to visit all cities exactly once, starting and ending at city 1.

I think it maybe a dp problem. I guess suppose you have solution for n-1, if you add n to path, it will add destroy the structure of the path in n-1 before. Example if you have 1-3-5-4-2-1 is the answer of n=5, if you add 6 to the path 6 may be between 1,3 or 3,5 or 5,4 ... Is it right solution or someone has others answer. Thank you for your help.