Security Camera 2

AtCoder

IDabc224_h

Time2000ms

Memory256MB

Difficulty—

We have a bipartite graph with $L$ vertices to the left and $R$ vertices to the right. Takahashi will install surveillance cameras in these vertices. Installing cameras incurs the following cost. * $A_i$ yen (the Japanese currency) for each camera installed in the $i$\-th $(1 \le i \le L)$ vertex to the left; * $B_j$ yen (the Japanese currency) for each camera installed in the $j$\-th $(1 \le j \le R)$ vertex to the right. It is allowed to install multiple cameras on the same vertex. Find the minimum amount of money needed to install cameras to satisfy the following condition. * For every pair of integers $(i, j)$ such that $1 \le i \le L, 1 \le j \le R$, there is a total of $C_{i,j}$ or more cameras installed in the $i$\-th vertex to the left and $j$\-th vertex to the right. ## Constraints * All values in input are integers. * $1 \le L,R \le 100$ * $1 \le A_i,B_i \le 10$ * $0 \le C_{i,j} \le 100$ ## Input Input is given from Standard Input in the following format: $L$ $R$ $A_1$ $A_2$ $\dots$ $A_L$ $B_1$ $B_2$ $\dots$ $B_R$ $C_{1,1}$ $C_{1,2}$ $\dots$ $C_{1,R}$ $C_{2,1}$ $C_{2,2}$ $\dots$ $C_{2,R}$ $\vdots$ $C_{L,1}$ $C_{L,2}$ $\dots$ $C_{L,R}$ [samples]

Samples

Input #1

Output #1

37

You can achieve the objective for $37$ yen as follows, which is the minimum amount required.

*   Install $2$ cameras on the $1$\-st vertex in the left.
*   Install $3$ cameras on the $2$\-nd vertex in the left.
*   Install $2$ cameras on the $3$\-rd vertex in the left.
*   Install $1$ camera on the $1$\-st vertex in the right.
*   Install $1$ camera on the $3$\-rd vertex in the right.

Input #2

Output #2

0

No camera may be needed.

Input #3

5 6
3 2 6 7 5
4 9 8 6 2 3
2 0 2 1 1 0
2 3 2 1 0 0
2 2 4 0 2 2
4 1 0 3 0 2
1 0 0 2 2 5

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Security Camera 2",
    "description": {
      "content": "We have a bipartite graph with $L$ vertices to the left and $R$ vertices to the right.   Takahashi will install surveillance cameras in these vertices.   Installing cameras incurs the following cost. ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc224_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a bipartite graph with $L$ vertices to the left and $R$ vertices to the right.  \nTakahashi will install surveillance cameras in these vertices.  \nInstalling cameras incurs the following cost.\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments