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

Trong đợt thử nghiệm công nghệ mới của MobiZone và VinaGone, CEO của hai tập đoàn viễn thông này là KTuấn và AnhDQ đã kí một hợp đồng liên kết giúp hai nhà cung cấp dịch vụ viễn thông này có thể sử dụng chung mạng lưới của nhau. Có N người tiến hành tham gia đợt thử nghiệm này. Biết rằng người thứ i cần trả một khoản chi phí là M_i nếu sử dụng dịch vụ của MobiZone, hoặc V_i nếu sử dụng dịch vụ của VinaGone; đồng thời hai người thứ i và j bất kì chấp nhận trả chung một khoản chi phí là C_ij nếu sử dụng dịch vụ của hai nhà cung cấp khác nhau (để trả phí cho dịch vụ liên kết).

Yêu cầu

Hãy tư vấn cho N người này lựa chọn một trong hai dịch vụ mạng sao cho tổng chi phí mà N người phải bỏ ra là nhỏ nhất. Cho biết chi phí nhỏ nhất đó.

Dữ liệu

- Dòng đầu tiên chứa số N.
- Dòng thứ hai chứa N số M_i.
- Dòng thứ ba chứa N số V_i.
- N dòng cuối cùng, mỗi dòng N số C_ij (C_ij = C_ji).

Kết quả

- Gồm một số duy nhất là chi phí nhỏ nhất tìm được.

Ví dụ

Dữ liệu:
3
1 1 10
10 10 1
0 0 1
0 0 1
1 1 0

Kết quả:
5

Giới hạn

- N ≤ 250.
- Các số còn lại trong Input không vượt quá 1000.