Giải bài trực tuyến

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 i^th people accepts to pay M_i to use MobiZone's service or V_i to use VinaGone's one; and any two people i^th and j^th accept to pay C_ij 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) M_i.
- The third line contains N number(s) V_i.
- The last N line(s), each of them contains N number(s) C_ij (C_ij = C_ji).

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.