시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB125907872.897%

문제

A wide river has n pillars of possibly different heights standing out of the water. They are arranged in a straight line from one bank to the other. We would like to build a bridge that uses the pillars as support. To achieve this we will select a subset of pillars and connect their tops into sections of a bridge. The subset has to include the first and the last pillar.

The cost of building a bridge section between pillars i and j is (hi − hj)2 as we want to avoid uneven sections, where hi is the height of the pillar i. Additionally, we will also have to remove all the pillars that are not part of the bridge, because they obstruct the river traffic. The cost of removing the i-th pillar is equal to wi. This cost can even be negative—some interested parties are willing to pay you to get rid of certain pillars. All the heights hi and costs wi are integers.

What is the minimum possible cost of building the bridge that connects the first and last pillar?

입력

The first line contains the number of pillars, n. The second line contains pillar heights hi in the order, separated by a space. The third line contains wi in the same order, the costs of removing pillars.

출력

Output the minimum cost for building the bridge. Note that it can be negative.

제한

  • 2 ≤ n ≤ 105
  • 0 ≤ hi ≤ 106
  • 0 ≤ |wi| ≤ 106

서브태스크 1 (30점)

  • n ≤ 1 000

서브태스크 2 (30점)

  • Optimal solution includes at most 2 additional pillars (besides the first and last)
  • |wi| ≤ 20

서브태스크 3 (40점)

  • No additional constraints

예제 입력 1

6
3 8 7 1 6 6
0 -1 9 1 2 0

예제 출력 1

17

채점 및 기타 정보

  • 예제는 채점하지 않는다.