Unlock Achievement

AtCoder

IDabc326_g

Time2000ms

Memory256MB

Difficulty—

There are $N$ skills numbered $1$ to $N$ and $M$ achievements numbered $1$ to $M$. Each skill has a positive integer level, and the initial level of every skill is $1$. You can pay a cost of $C_i$ yen to increase the level of skill $i$ by $1$. You can do this as many times as you want. Achievement $i$ is achieved when the following condition is satisfied for every $j=1,\ldots,N$, for which you will receive a reward of $A_i$ yen. * Condition: The level of skill $j$ is at least $L_{i,j}$. Find the maximum possible total reward obtained minus the total cost required when appropriately choosing how to raise the skill levels. ## Constraints * $1 \leq N,M \leq 50$ * $1 \leq L_{i,j} \leq 5$ * $1 \leq A_i,C_i \leq 10^6$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $C_1$ $\ldots$ $C_N$ $A_1$ $\ldots$ $A_M$ $L_{1,1}$ $\ldots$ $L_{1,N}$ $\vdots$ $L_{M,1}$ $\ldots$ $L_{M,N}$ [samples]

Samples

Input #1

Output #1

80

There are two skills. It costs $10$ yen to raise the level of skill $1$ and $20$ yen to raise the level of skill $2$.  
There are two achievements. Achievement $1$ is achieved when skill $1$ is at least level $3$ and skill $2$ is at least level $1$, for which you will receive $100$ yen. Achievement $2$ is achieved when skill $1$ is at least $1$ and skill $2$ is at least level $4$, for which you will receive $50$ yen.
By raising skill $1$ to level $3$ and skill $2$ to level $1$, you will receive the reward of $100$ yen for the cost of $20$ yen, and the balance is $80$ yen.

Input #2

Output #2

70

By raising skill $1$ to level $3$ and skill $2$ to level $4$, you will receive the reward of $150$ yen for the cost of $80$ yen, and the balance is $70$ yen.

Input #3

10 10
10922 23173 32300 22555 29525 16786 3135 17046 11245 20310
177874 168698 202247 31339 10336 14825 56835 6497 12440 110702
2 1 4 1 3 4 4 5 1 4
2 3 4 4 5 3 5 5 2 3
2 3 5 1 4 2 2 2 2 5
3 5 5 3 5 2 2 1 5 4
3 1 1 4 4 1 1 5 3 1
1 2 3 2 4 2 4 3 3 1
4 4 4 2 5 1 4 2 2 2
5 3 1 2 3 4 2 5 2 2
5 4 3 4 3 1 5 1 5 4
2 3 2 5 2 3 1 2 2 4

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Unlock Achievement",
    "description": {
      "content": "There are $N$ skills numbered $1$ to $N$ and $M$ achievements numbered $1$ to $M$. Each skill has a positive integer level, and the initial level of every skill is $1$. You can pay a cost of $C_i$ yen",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc326_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ skills numbered $1$ to $N$ and $M$ achievements numbered $1$ to $M$.\nEach skill has a positive integer level, and the initial level of every skill is $1$.\nYou can pay a cost of $C_i$ yen...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments