题目描述

有一座建造已久的桥梁需要进行加固计。桥梁有 $n$ 根支柱，第 $1$ 根与第 $n$ 根分别在河流的两岸，第 $i$ 根支柱的高度为 $h_i$。

工程师打算在 $n$ 根支柱中选择一些进行加固，并且在加固的支柱之间，铺设辅材。第一根和最后一根支柱都是必须加固的，假设在第 $i$ 根支撑柱与第 $j$ 根支柱之间铺设辅材，所需的费用为$(h_i-h_j)^2$。

对于放弃加固的支柱，必须拆除，第 $i$ 根支柱的拆除费用为 $c_i$。请计算一下，选择加固哪些支柱，才能使加固工程的总费用达到最低呢？

输入格式

第一行， 一个正整数$n$ 接下来$n$行，每行两个正整数$h_i,c_i$

输出格式

输出连通桥梁的最小代价

4
1 2
4 4
6 3
3 2

11

样例解释 1

直接从1连到4，花费为4，拆除费用为4+3=7，总花费最低为11

6
5 1
2 2
7 9
2 2
1 2
2 2

20

数据范围

• 对于 $30\%$ 的数据， $2 \leq n\leq 100$；
• 对于 $60\%$ 的数据， $2 \leq n\leq 10^4$；
• 对于 $100\%$ 的数据， $2\leq n \leq 10^5$，$1\leq h_i\leq 10^6$，$|c_i|\leq 10^6$。