#include <bits/stdc++.h>
#define ent '\n'
#define f first
#define s second

typedef long long ll;
using namespace std;
const int maxn = 1e6+12;

pair<ll, int> dp[maxn];
vector<int> g[maxn];
bool was[maxn];
vector<int> t;
int L[maxn];
int R[maxn];
int n, m;

struct line{
    ll k, b;
    int c;
};

bool check(line nw, line last, line prl){
    if((nw.b - prl.b) * (prl.k - last.k) <= (last.b - prl.b) * (prl.k - nw.k))return 1;
    return 0;
}

int ptr = 0;
vector<line> l;

void add(line x){
    while(l.size() && l.back().k == x.k && l.back().b > x.b){
        l.pop_back();
    }
    if(l.size() && l.back().k == x.k && l.back().b <= x.b){
        return;
    }
    while(l.size()>1 && check(x, l.back(), l[l.size()-2])){
        l.pop_back();
    }
    l.push_back(x);
}

pair<ll, int> get(ll x){
    if(!l.size()){
        return {1e18, 1e9};
    }
    if(ptr >= l.size()){
        ptr = l.size()-1;
    }
    while(ptr + 1 < l.size() && l[ptr].k * x + l[ptr].b > l[ptr+1].k * x + l[ptr+1].b){
        ptr++;
    }
    return {l[ptr].k * x + l[ptr].b, l[ptr].c + 1};
}

int check(ll k){
    add({0, 0, 0});
    for(int &i:t){
        dp[i] = get(i);
        dp[i].f += i * 1ll * i + k;
        for(int &j:g[i]){
            ll b = j * 1ll * j + dp[R[j]].f, c = dp[R[j]].s;
            if(R[j] > j) b -= (R[j] - j) * 1ll * (R[j] - j);
            add(line(-2 * j, b, c));
        }
    }
    l.clear();
    ptr = 0;
    return dp[m].s;
}

long long take_photos(int N, int M, int k, vector<int> rr, vector<int> c){
    n = N, m = M;
    for(int i=1;i<=m;i++){
        L[i] = 1e9;
    }
    m = 0;
    for(int i=0;i<n;i++){
        if(rr[i] < c[i]){
            swap(rr[i], c[i]);
        }
        rr[i]++, c[i]++;
        L[rr[i]] = min(L[rr[i]], c[i]);
        R[c[i]] = max(R[c[i]], rr[i]);
        for(int x=-1;x<=0;x++){
            was[rr[i]+x] = was[c[i]+x] = 1;
        }
        m = max(m, rr[i]);
    }
    was[1] = 1;
    for(int i=1;i<=m;i++){
        R[i] = max(R[i], R[i-1]);
        if(!was[i]) continue;
        t.push_back(i);
        g[max(R[i], i)].push_back(i);
    }
#include <bits/stdc++.h>
#define ent '\n'
#define f first
#define s second

    typedef long long ll;
    using namespace std;
    const int maxn = 1e6+12;

    pair<ll, int> dp[maxn];
    vector<int> g[maxn];
    bool was[maxn];
    vector<int> t;
    int L[maxn];
    int R[maxn];
    int n, m;

    struct line{
        ll k, b;
        int c;
    };

    bool check(line nw, line last, line prl){
        if((nw.b - prl.b) * (prl.k - last.k) <= (last.b - prl.b) * (prl.k - nw.k))return 1;
        return 0;
    }

    int ptr = 0;
    vector<line> l;

    void add(line x){
        while(l.size() && l.back().k == x.k && l.back().b > x.b){
            l.pop_back();
        }
        if(l.size() && l.back().k == x.k && l.back().b <= x.b){
            return;
        }
        while(l.size()>1 && check(x, l.back(), l[l.size()-2])){
            l.pop_back();
        }
        l.push_back(x);
    }

    pair<ll, int> get(ll x){
        if(!l.size()){
            return {1e18, 1e9};
        }
        if(ptr >= l.size()){
            ptr = l.size()-1;
        }
        while(ptr + 1 < l.size() && l[ptr].k * x + l[ptr].b > l[ptr+1].k * x + l[ptr+1].b){
            ptr++;
        }
        return {l[ptr].k * x + l[ptr].b, l[ptr].c + 1};
    }

    int check(ll k){
        add({0, 0, 0});
        for(int &i:t){
            dp[i] = get(i);
            dp[i].f += i * 1ll * i + k;
            for(int &j:g[i]){
                ll b = j * 1ll * j + dp[R[j]].f, c = dp[R[j]].s;
                if(R[j] > j) b -= (R[j] - j) * 1ll * (R[j] - j);
                add(line(-2 * j, b, c));
            }
        }
        l.clear();
        ptr = 0;
        return dp[m].s;
    }

    long long take_photos(int N, int M, int k, vector<int> rr, vector<int> c){
        n = N, m = M;
        for(int i=1;i<=m;i++){
            L[i] = 1e9;
        }
        m = 0;
        for(int i=0;i<n;i++){
            if(rr[i] < c[i]){
                swap(rr[i], c[i]);
            }
            rr[i]++, c[i]++;
            L[rr[i]] = min(L[rr[i]], c[i]);
            R[c[i]] = max(R[c[i]], rr[i]);
            for(int x=-1;x<=0;x++){
                was[rr[i]+x] = was[c[i]+x] = 1;
            }
            m = max(m, rr[i]);
        }
        was[1] = 1;
        for(int i=1;i<=m;i++){
            R[i] = max(R[i], R[i-1]);
            if(!was[i]) continue;
            t.push_back(i);
            g[max(R[i], i)].push_back(i);
        }
        ll val = 0;
        for(ll l = -2e12, r = 2e12; l <= r;){
            ll mid = l + r >> 1;
            if(check(mid) <= k){
                val = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        ll l = val, r = 2e12;
        while(r - l > 10){
            ll m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
            check(m1); ll lx = dp[m].f - dp[m].s * m1;
            check(m2); ll rx = dp[m].f - dp[m].s * m2;
            if(lx < rx){
                r = m2;
            }
            else{
                l = m1;
            }
        }
        ll ans = 1e18;
        for(ll i=l;i<=r;i++){
            check(i);
            ans = min(ans, dp[m].f - dp[m].s * i);
        }
        return ans;
    }
    ll val = 0;
    for(ll l = -2e12, r = 2e12; l <= r;){
        ll mid = l + r >> 1;
        if(check(mid) <= k){
            val = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    ll l = val, r = 2e12;
    while(r - l > 10){
        ll m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        check(m1); ll lx = dp[m].f - dp[m].s * m1;
        check(m2); ll rx = dp[m].f - dp[m].s * m2;
        if(lx < rx){
            r = m2;
        }
        else{
            l = m1;
        }
    }
    ll ans = 1e18;
    for(ll i=l;i<=r;i++){
        check(i);
        ans = min(ans, dp[m].f - dp[m].s * i);
    }
    return ans;
}

answer.code: In function ‘long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)’:
answer.code:120:45: error: a function-definition is not allowed here before ‘{’ token
  120 |     bool check(line nw, line last, line prl){
      |                                             ^
answer.code:128:21: error: a function-definition is not allowed here before ‘{’ token
  128 |     void add(line x){
      |                     ^
answer.code:141:28: error: a function-definition is not allowed here before ‘{’ token
  141 |     pair<ll, int> get(ll x){
      |                            ^
answer.code:154:20: error: a function-definition is not allowed here before ‘{’ token
  154 |     int check(ll k){
      |                    ^
answer.code:170:78: error: a function-definition is not allowed here before ‘{’ token
  170 |     long long take_photos(int N, int M, int k, vector<int> rr, vector<int> c){
      |                                                                              ^
answer.code:232:8: error: conflicting declaration ‘ll l’
  232 |     ll l = val, r = 2e12;
      |        ^
answer.code:126:18: note: previous declaration as ‘std::vector<take_photos(int, int, int, std::vector<int>, std::vector<int>)::line> l’
  126 |     vector<line> l;
      |                  ^
answer.code:233:13: error: no match for ‘operator-’ (operand types are ‘ll’ {aka ‘long long int’} and ‘std::vector<take_photos(int, int, int, std::vector<int>, std::vector<int>)::line>’)
  233 |     while(r - l > 10){
      |           ~ ^ ~
      |           |   |
      |           |   std::vector<take_photos(int, int, int, std::vector<int>, std::vector<int>)::line>
      |           ll {aka long long int}
In file included from /usr/include/c++/13/bits/stl_algobase.h:67,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_iterator.h:625:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&)’
  625 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:625:5: note:   template argument deduction/substitution failed:
answer.code:233:15: note:   mismatched types ‘const std::reverse_iterator<_IteratorL>’ and ‘ll’ {aka ‘long long int’}
  233 |     while(r - l > 10){
      |               ^
/usr/include/c++/13/bits/stl_iterator.h:1800:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)’
 1800 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1800:5: note:   template argument deduction/substitution failed:
answer.code:233:15: note:   mismatched types ‘const std::move_iterator<_IteratorL>’ and ‘ll’ {aka ‘long long int’}
  233 |     while(r - l > 10){
      |               ^
In file included from /usr/include/c++/13/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127:
/usr/include/c++/13/complex:365:5: note: candidate: ‘template<class _Tp> constexpr std::complex<_Tp> std::operator-(const complex<_Tp>&, const complex<_Tp>&)’
  365 |     operator-(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/13/complex:365:5: note:   template argument deduction/substitution failed:
answer.code:233:15: note:   mismatched types ‘const std::complex<_Tp>’ and ‘ll’ {aka ‘long long int’}
  233 |     while(r - l > 10){
      |               ^
/usr/include/c++/13/complex:374:5: note: candidate: ‘template<class _Tp> constexpr std::complex<_Tp> std::operator-(const complex<_Tp>&, const _Tp&)’
  374 |     operator-(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/13/complex:374:5: note:   template argument deduction/substitution failed:
answer.code:233:15: note:   mismatched types ‘const std::complex<_Tp>’ and ‘ll’ {aka ‘long long int’}
  233 |     while(r - l > 10){
      |               ^
/usr/include/c++/13/complex:383:5: note: candidate: ‘template<class _Tp> constexpr std::complex<_Tp> std::operator-(const _Tp&, const complex<_Tp>&)’
  383 |     operator-(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/13/complex:383:5: note:   template argument deduction/substitution failed:
answer.code:233:15: note:   ‘std::vector<take_photos(int, int, int, std::vector<int>, std::vector<int>)::line>’ is not derived from ‘const std::complex<_Tp>’
  233 |     while(r - l > 10){
      |               ^
/usr/include/c++/13/complex:460:5: note: candidate: ‘template<class _Tp> constexpr std::complex<_Tp> std::operator-(const complex<_Tp>&)’
  460 |     operator-(const complex<_Tp>& __x...