#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
const int INF = 2e9;
const ll INFLL = 4e18;
const int N = 1e5+1;
const int mod = 998244353;
struct point{
int x,y;
point() {}
point(int _x, int _y) : x(_x), y(_y) {}
int64_t square_size(){
int64_t ans = max(y+1-x,0);
return ans*ans;
}
};
point unite(const point a, const point b){
int nwx = min(a.x,b.x);
int nwy = max(a.y,b.y);
return point(nwx,nwy);
}
point intersection(const point a, const point b){
int nwx = max(a.x,b.x);
int nwy = min(a.y,b.y);
return point(nwx,nwy);
}
bool cmp(point a, point b){
if(a.x == b.x) return a.y > b.y;
else return a.x < b.x;
}
void dnc(vector<vector<pair<int64_t,point>>> &dp, int k, vector<point> &p, int lt_l, int lt_r, int rt_l, int rt_r){
if(rt_r < rt_l) return;
int rt_mid = (rt_l + rt_r) / 2;
int lt_mid = lt_l;
for(int i = lt_l; i <= lt_r && i <= rt_mid; i++){
point curr_pt = unite(p[rt_mid],p[i]);
int64_t curr = curr_pt.square_size();
if(i) curr += dp[i-1][k-1].first - intersection(dp[i-1][k-1].second, curr_pt).square_size();
if(curr <= dp[rt_mid][k].first){
dp[rt_mid][k] = make_pair(curr,curr_pt);
lt_mid = i;
}
}
dnc(dp, k, p, lt_l, lt_mid, rt_l, rt_mid - 1);
dnc(dp, k, p, lt_mid, lt_r, rt_mid + 1, rt_r);
}
int64_t take_photos(int n, int m, int k, vector<int> r, vector<int> c){
point temp[n];
for(int i = 0; i < n; i++){
if(r[i] <= c[i]) temp[i] = point(r[i],c[i]);
else temp[i] = point(c[i],r[i]);
}
sort(temp,temp+n,cmp);
vector<point> p;
int threshold = -1;
for(int i = 0; i < n; i++){
if(temp[i].y > threshold){
// cout << temp[i].x << " " << temp[i].y << "\n";
p.pb(temp[i]);
threshold = temp[i].y;
}
}
n = p.size();
vector<vector<pair<int64_t,point>>> dp(n, vector<pair<int64_t,point>>(k,make_pair(int64_t(INFLL), point(-1,-1))));
for(int i = 0; i < n; i++) dp[i][0] = make_pair(unite(p[i],p[0]).square_size(), unite(p[i],p[0]));
for(int j = 1; j < k; j++) dnc(dp, j, p, 0, n-1, 0, n-1);
// for(int i = 0; i < k; i++){
// for(int j = 0; j < n; j++){
// cout << dp[j][i] << " ";
// }
// cout << "\n";
// }
return dp[n-1][k-1].first;
}
void solve(){
int n,m,k;
cin >> n >> m >> k;
vector<int> r(n),c(n);
for(int i = 0; i < n; i++) cin >> r[i];
for(int i = 0; i < n; i++) cin >> c[i];
cout << take_photos(n,m,k,r,c) << "\n";
}
// int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// int t = 1;
// // cin >> t;
// while(t--) solve();
// }
