MOBIVINA - MobiZone vs VinaGone

KTuan and AnhDQ, CEOs of two telecommunication corporations MobiZone and VinaGone have signed a contract to use their network in common. N people have accepted to try this new service. The ith people accepts to pay Mi to use MobiZone's service or Vi to use VinaGone's one; and any two people ith and jth accept to pay Cij in common whether they use different services (the network cost).

Request

Find a way of choosing networks for N people satisfying the sum of total cost is minimum.

Input

- The first line contains number N.
- The second line contains N number(s) Mi.
- The third line contains N number(s) Vi.
- The last N line(s), each of them contains N number(s) Cij (Cij = Cji).

Output

- Contains the minimum total cost.

Example

Input:
3
1 1 10
10 10 1
0 0 1
0 0 1
1 1 0

Output:
5

Limitations

- N ≤ 250.
- The remaining numbers of Input do not exceed 1000.


Added by:AnhDQ
Date:2009-06-08
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Mr Tuan Khuc Anh - NTU (Singapore)

hide comments
2021-01-12 04:36:49
Another similar problem: LightOJ 1361 - Component Placement
2020-04-02 12:11:29
The last line of the statement means if two guys i and j use different services then they pay Cij (=Cji) once.
2013-03-27 15:32:11 যোবায়ের
@Alex Abbas, I think the possible explanation is, you assign person1 with Mobi, person2 with Mobi and person3 with Vina. Then they need to pay 1 + 1 + 1 individually. Also, person1 and person3 are using different network, so they pay C[1][3] more, same as person2 and person3, C[2][3] more. totalling 3 + 1 + 1 = 5

Last edit: 2013-09-19 05:40:15
2013-02-26 15:28:06 Alex Abbas
I don't understand whether we need to connect all services to all people or just one service can u explain the input/output sample please...
2012-08-30 16:56:31 Ajey Golsangi
The problem statement is unclear. Please rectify the grammar in the problem statement.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.