#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 convex_hull_point{
int m;
int64_t c;
convex_hull_point () {}
convex_hull_point(const int &_m, const int64_t &_c) : m(_m), c(_c) {}
convex_hull_point operator - (const convex_hull_point nw){
return convex_hull_point(m-nw.m,c-nw.c);
}
};
int64_t cross(convex_hull_point a, convex_hull_point b){
return(a.m*b.c - a.c*b.m);
}
int64_t eval(convex_hull_point &a, int x){
return (1ll*a.m*x + a.c);
}
struct convex_hull_with_ind : convex_hull_point{
int ind;
convex_hull_with_ind() : convex_hull_point() {}
convex_hull_with_ind(int _m, ll _c, int _ind) : convex_hull_point(_m, _c), ind(_ind) {}
};
struct convex_hull{
vector<convex_hull_with_ind> hull;
int ind = 0;
void add(convex_hull_with_ind x){
int n = hull.size();
while(n > 1 && cross(x-hull[n-1], hull[n-1] - hull[n-2]) < 0){
--n;
hull.pop_back();
}
hull.push_back(x);
if(ind > n) ind = n;
}
convex_hull_with_ind query(int x){
while(ind < hull.size() - 1 && eval(hull[ind],x) <= eval(hull[ind + 1],x)) ind++;
return hull[ind];
}
};
struct point{
int x,y;
point() {}
point(const int &_x, const 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(const point &a, const point &b){
if(a.x == b.x) return a.y > b.y;
else return a.x < b.x;
}
pair<int64_t,int> get_cost_and_partitions(vector<point> &p, int64_t cost){
int n = p.size();
int64_t dp[n+1];
int cnt[n+1];
dp[0] = cnt[0] = 0;
convex_hull my_hull;
for(int i = 1; i <= n; i++){
int xi = p[i-1].x;
int yi = p[i-1].y + 1;
ll common_area;
if(i == 1) common_area = 0;
else common_area = intersection(p[i-1],p[i-2]).square_size();
my_hull.add(convex_hull_with_ind(2*xi, common_area - 1ll*xi*xi - dp[i-1], i-1));
convex_hull_with_ind temp = my_hull.query(yi);
dp[i] = 1ll*yi*yi + cost - 1ll*temp.m*yi - temp.c;
cnt[i] = cnt[temp.ind] + 1;
}
return make_pair(dp[n],cnt[n]);
}
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();
int64_t lt = 0, rt = 1ll*m*m + 1;
while(rt-lt > 1){
int64_t mid = (lt+rt)/2;
auto it = get_cost_and_partitions(p, mid);
if(it.second >= k) lt = mid;
else rt = mid;
// cout << mid << " " << it.first << " " << it.second << "\n";
}
auto it = get_cost_and_partitions(p,lt);
return it.first - 1ll*k*lt;
}
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();
// }
