#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
const int mod = 1e9 + 7;
const ll inf = 2e15;
const int N = 5e2 + 15;
ll dp[N][N];
int l[N], r[N];
int ord[N];
vector <pii> tmp;
ll val[N];
inline ll sq(ll x) {
return x * x;
}
inline void Min(ll &a, ll b) {
a = min(a, b);
}
struct line {
int k;
ll b;
line(int k, ll b) : k(k), b(b) {}
inline ll get(int x) {
return k * x + b;
}
inline ld intersect(line nw) {
return (ld)(b - nw.b) / (nw.k - k);
}
};
vector <line> hull;
int ptr;
inline void add(line nw) {
while(hull.size() > 1 && hull[hull.size() - 2].intersect(nw) <= hull.back().intersect(nw))
hull.ppb();
hull.pb(nw);
}
inline ll get(int x) {
while(ptr + 1 < hull.size() && hull[ptr].get(x) >= hull[ptr + 1].get(x))
++ptr;
return hull[ptr].get(x);
}
ll take_photos(int n, int m, int k, std::vector<int> row, std::vector<int> col) {
for(int i = 0; i < n; ++i) {
l[i+1] = min(row[i], col[i]) + 1;
r[i+1] = max(row[i], col[i]) + 1;
ord[i+1] = i+1;
}
sort(ord + 1, ord + 1 + n, [&](int x, int y) {
return mp(l[x], -r[x]) < mp(l[y], -r[y]);
});
for(int i = 1; i <= n; ++i)
if(tmp.empty() || !(tmp.back().f <= l[ord[i]] && tmp.back().se >= r[ord[i]]))
tmp.pb(mp(l[ord[i]], r[ord[i]]));
n = tmp.size();
for(int i = 1; i <= n; ++i) {
l[i] = tmp[i-1].f, r[i] = tmp[i-1].se;
val[i] = sq(max(0, r[i-1] - l[i] + 1));
}
for(int i = 0; i < N; ++i)
for(int j = 0; j < N; ++j)
dp[i][j] = inf;
dp[0][0] = 0;
for(int t = 1; t <= k; ++t) {
hull.clear();
ptr = 0;
for(int i = 1; i <= n; ++i) {
line nw = *new line(-2 * l[i], sq(l[i]) + dp[i-1][t-1] - val[i]);
add(nw);
Min(dp[i][t], sq(r[i] + 1) + get(r[i] + 1));
}
}
return *min_element(dp[n] + 1, dp[n] + 1 + k);
}
