Tiles
Limits: 2 sec., 256 MiB
Kerem and Asli are moving into their new apartment!
The only thing left to do is to paint tiles in the kitchen. There are \(N\) tiles in total to paint. Kerem chose three distinct colors and for each tile he estimated the cost of painting this tile in each of three colors. Note that different tiles may have different cost of painting for the same color.
But Asli thinks that using all three colors would be a bit too much. So they decided to paint all tiles in just two (or one) colors in a way that minimizes the total cost.
Your task is to find the minimum total cost of painting all tiles while not using all three colors.
Input
The first line contains a single integer \(N\) — the number of tiles. The second line contains \(N\) space-separated integers \(a_1, a_2 ..., a_N\) — the costs of painting the corresponding tiles in the first color. The third line contains \(N\) space-separated integers \(b_1, b_2 ..., b_N\) — the costs of painting the corresponding tiles in the second color. The fourth line contains \(N\) space-separated integers \(c_1, c_2 ..., c_N\) — the costs of painting the corresponding tiles in the third color.
Output
In the only line print a single integer — the answer to the problem.
Constraints
\(1 \le N \le 10^5\),
\(0 \le a_i, b_i, c_i \le 10^4\).
Samples
Input (stdin) | Output (stdout) |
---|---|
4 2 5 1 3 3 7 1 4 7 4 1 9 | 10 |
Notes
The best decision is to paint the first, the third and the fourth tiles in the first color (2+1+3), and the second one in the third color (4). The total cost is 10.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|