{"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$ terms in the original sequence.\nOne 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.\nHere, 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$.\n\n## Constraints\n\n*   $1 ≦ N ≦ 10^3$\n*   $1 ≦ M ≦ 10^3$\n*   Let the $j$\\-th term in $A_i$ be $A_{(i,j)}$, then $1 ≦ A_{(i,j)} ≦ 10^9$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_{(1,1)}$ $A_{(1,2)}$ … $A_{(1,M)}$\n$A_{(2,1)}$ $A_{(2,2)}$ … $A_{(2,M)}$\n:\n$A_{(N,1)}$ $A_{(N,2)}$ … $A_{(N,M)}$\n\n## Partial Scores\n\n*   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$.\n*   In the test set worth another $800$ points, $A_{(i,j)} ≦ 80$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"asaporo_a","tags":[],"sample_group":[["3 3\n2 3 1\n2 1 2\n2 6 3","1\n\nTakahashi can achieve his objective by casting the spell on $A_2$ once to turn it into $(2 , 3 , 5)$."],["3 3\n3 2 10\n10 5 4\n9 1 9","\\-1\n\nIn this case, Takahashi cannot achieve his objective by casting the spell any number of times."],["5 5\n2 6 5 6 9\n2 6 4 9 10\n2 6 8 6 7\n2 1 7 3 8\n2 1 4 8 3","11"]],"created_at":"2026-03-03 11:01:14"}}