AtCoder. 019 Pick Two(6)

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int n = atoi(bf.readLine());
    String[] split = bf.readLine().split(" ");
    int[] a = new int[2*n];
    int[][] dp = new int[2*n][2*n];

    for(int i = 0; i < 2 * n; i++) a[i] = atoi(split[i]);

    for(int i = 0; i < 2 * n; i++) {
      for(int j = (((i%2)&1)==0) ? 1 : 0; j < i; j+=2) {
        int min = Integer.MAX_VALUE;
        for(int k = j; k < i; k+=2) min = Math.min(min, Math.abs(a[i] - a[k]) + (k > j ? dp[j][k - 1] : 0) + (k + 1 < i - 1 ? dp[k + 1][i - 1] : 0));
        dp[j][i] = min;
      }
    }
    System.out.println(dp[0][2 * n - 1]);
  }

  static int atoi(String s) { return Integer.parseInt(s); }
}