Minimal price P20023


Statement
 

pdf   zip

thehtml

You have n tasks to do, and n workers that can do them. For each task 1 ≤ in and each worker 1 ≤ jn, p[i][j] is the price that the worker i does the task j.

Write a program that computes the minimal price of assigning exactly one different task to each worker.

Input

Input consists of a natural 1 ≤ n ≤ 10, followed by p, the matrix n × n of prices (n lines with n natural numbers between 1 and 1000).

Output

Your program must print the minimal price of assigning exactly one different task to each worker.

Observation

There are algorithms of polynomial cost to solve this problem, but are difficult to program. Implement a backtracking.

Public test cases
  • Input

    3
    5 2 1
    2 1 3
    1 3 7
    

    Output

    3
    
  • Input

    4
    2 5 7 9
    2 2 2 2
    2 1 8 3
    2 9 9 8
    

    Output

    12
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python