Given an array of size N*N (1<=N<=1000) . We can select only one element from each row. Once an element is selected from a given row the column containing that element is freezed. Now for further rows we can't select any element from that column. The problem is to minimize the sum of selected elements .

I am thinking of some dp approach but size of N seems a bit large. Please suggest any other way to solve this problem. Thanks.