#include "railroad_c.h"
#include <string.h>
#define N 16
#define INF 0x3f3f3f3f3f3f3f3f
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
long long plan_roller_coaster(int n, int *aa, int *bb) {
static long long dp[1 << N][N];
int i, j, b;
long long x;
for (b = 1; b < 1 << n; b++)
memset(dp[b], 0x3f, n * sizeof *dp[b]);
for (i = 0; i < n; i++)
dp[1 << i][i] = 0;
for (b = 1; b < 1 << n; b++)
for (i = 0; i < n; i++) {
x = dp[b][i];
if (x == INF)
continue;
for (j = 0; j < n; j++)
if ((b & 1 << j) == 0)
dp[b | 1 << j][j] = min(dp[b | 1 << j][j], x + max(bb[i] - aa[j], 0));
}
x = INF;
for (i = 0; i < n; i++)
x = min(x, dp[(1 << n) - 1][i]);
return x;
}
