Statement

Edoardo is preparing the infrastructure for the online contest of the current OIS edition's final round. As always, the contest will be managed using CMS, which is a platform composed of N services that all need to be executed in order for it to be able to work properly. To distribute the load, these services will be executed on two cloud servers. Edoardo needs to decide how to assign each service to one of the two servers. For the i-th service, it costs A_i euro to run it on the first server and B_i euro to execute it on the second one. But there is more! Edoardo will also have to pay for the bandwidth used by services that need to communicate and that are assigned to different servers. This means that, if the i-th service is assigned to the first server and the j-th one to the second, then Edoardo will also have to pay C_ij euro. What is the minimum amount of euro Edoardo will spend, if he assigns the services on the two servers optimally?