Yakiniku Restaurants

AtCoder

IDarc067_d

Time2000ms

Memory256MB

Difficulty—

There are $N$ barbecue restaurants along a street. The restaurants are numbered $1$ through $N$ from west to east, and the distance between restaurant $i$ and restaurant $i+1$ is $A_i$. Joisino has $M$ tickets, numbered $1$ through $M$. Every barbecue restaurant offers barbecue meals in exchange for these tickets. Restaurant $i$ offers a meal of _deliciousness_ $B_{i,j}$ in exchange for ticket $j$. Each ticket can only be used once, but any number of tickets can be used at a restaurant. Joisino wants to have $M$ barbecue meals by starting from a restaurant of her choice, then repeatedly traveling to another barbecue restaurant and using unused tickets at the restaurant at her current location. Her eventual _happiness_ is calculated by the following formula: "(The total deliciousness of the meals eaten) - (The total distance traveled)". Find her maximum possible eventual happiness. ## Constraints * All input values are integers. * $2≤N≤5×10^3$ * $1≤M≤200$ * $1≤A_i≤10^9$ * $1≤B_{i,j}≤10^9$ ## Input The input is given from Standard Input in the following format: $N$ $M$ $A_1$ $A_2$ $...$ $A_{N-1}$ $B_{1,1}$ $B_{1,2}$ $...$ $B_{1,M}$ $B_{2,1}$ $B_{2,2}$ $...$ $B_{2,M}$ $:$ $B_{N,1}$ $B_{N,2}$ $...$ $B_{N,M}$ [samples]

Samples

Input #1

Output #1

11

The eventual happiness can be maximized by the following strategy: start from restaurant $1$ and use tickets $1$ and $3$, then move to restaurant $2$ and use tickets $2$ and $4$.

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Yakiniku Restaurants",
    "description": {
      "content": "There are $N$ barbecue restaurants along a street. The restaurants are numbered $1$ through $N$ from west to east, and the distance between restaurant $i$ and restaurant $i+1$ is $A_i$. Joisino has $M",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc067_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ barbecue restaurants along a street. The restaurants are numbered $1$ through $N$ from west to east, and the distance between restaurant $i$ and restaurant $i+1$ is $A_i$.\nJoisino has $M...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments