Takahashi the Magician

AtCoder

IDasaporo_a

Time2000ms

Memory256MB

Difficulty—

Takahashi is a magician. He can cast a spell on an integer sequence $(a_1,a_2,...,a_M)$ with $M$ terms, to turn it into another sequence $(s_1,s_2,...,s_M)$, where $s_i$ is the sum of the first $i$ terms in the original sequence. One day, he received $N$ integer sequences, each with $M$ terms, and named those sequences $A_1,A_2,...,A_N$. He will try to cast the spell on those sequences so that $A_1 < A_2 < ... < A_N$ will hold, where sequences are compared lexicographically. Let the action of casting the spell on a selected sequence be one cast of the spell. Find the minimum number of casts of the spell he needs to perform in order to achieve his objective. Here, for two sequences $a = (a_1,a_2,...,a_M), b = (b_1,b_2,...,b_M)$ with $M$ terms each, $a < b$ holds lexicographically if and only if there exists $i (1 ≦ i ≦ M)$ such that $a_j = b_j (1 ≦ j < i)$ and $a_i < b_i$. ## Constraints * $1 ≦ N ≦ 10^3$ * $1 ≦ M ≦ 10^3$ * Let the $j$\-th term in $A_i$ be $A_{(i,j)}$, then $1 ≦ A_{(i,j)} ≦ 10^9$. ## Input The input is given from Standard Input in the following format: $N$ $M$ $A_{(1,1)}$ $A_{(1,2)}$ … $A_{(1,M)}$ $A_{(2,1)}$ $A_{(2,2)}$ … $A_{(2,M)}$ : $A_{(N,1)}$ $A_{(N,2)}$ … $A_{(N,M)}$ ## Partial Scores * In the test set worth $200$ points, Takahashi can achieve his objective by at most $10^4$ casts of the spell, while keeping the values of all terms at most $10^9$. * In the test set worth another $800$ points, $A_{(i,j)} ≦ 80$. [samples]

Samples

Input #1

Output #1

1

Takahashi can achieve his objective by casting the spell on $A_2$ once to turn it into $(2 , 3 , 5)$.

Input #2

Output #2

\-1

In this case, Takahashi cannot achieve his objective by casting the spell any number of times.

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Takahashi the Magician",
    "description": {
      "content": "Takahashi is a magician. He can cast a spell on an integer sequence $(a_1,a_2,...,a_M)$ with $M$ terms, to turn it into another sequence $(s_1,s_2,...,s_M)$, where $s_i$ is the sum of the first $i$ te",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "asaporo_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi is a magician. He can cast a spell on an integer sequence $(a_1,a_2,...,a_M)$ with $M$ terms, to turn it into another sequence $(s_1,s_2,...,s_M)$, where $s_i$ is the sum of the first $i$ te...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments