Jak zminimalizować sumę kwadratu?

Cześć! Mam do rozwiązania takie zadanie, że na wejściu mamy daną pewną liczbę 'n' (1 <= n <= 1000), a następnie kwadratową tabelkę n*n (przy czym każdy element jest z przedziału 1...10^6). Teraz mamy usunąć jeden wierz i jedną kolumnę tak, aby suma wszystkich elementów tabelki była jak najmniejsza i wypisać tą sumę. Dla dokładniejszego zrozumienia, przedstawiam tutaj test przykładowy:
Wejście:
4
2 0 1 2
5 7 0 3
1 1 9 1
0 1 0 2
Wyjście:
10

(ponieważ możemy usunąć drugi wiersz i trzecią kolumnę)

Moim pierwszym pomysłem było aby od sumy wszystkich elementów odjąć kolumnę o największej sumie oraz wiersz o największej sumie i dodać do tego element, który leży na przecięciu tej kolumny i wiersza (dodać, ponieważ element na przecięciu nie może być liczony dwa razy). Niestety działa tylko dla 1/3 wszystkich testów.

#include <iostream>
using namespace std;

unsigned tb[1000][1000],ty[1000],tx[1000];

int main()
  {
   unsigned n,sum=0,v;
   cin>>n;
   for(unsigned y=0;y<n;++y)
     {
      for(unsigned x=0;x<n;++x)
        {
         cin>>v;
         tb[y][x]=v;
         ty[y]+=v;
         tx[x]+=v;
         sum+=v;
        }
     }
   unsigned pv=0;
   for(unsigned y=0;y<n;++y)
     {
      for(unsigned x=0;x<n;++x)
        {
         v=ty[y]+tx[x]-tb[y][x];
         if(pv<v) pv=v;
        }
     }
   cout<<sum-pv<<endl;
   return 0;
  }