This page is still under construction.

Parts of this page are still being built. What you see may change.

Hive

Time limit1sMemory limit256 MB

Summary
Each rabbit walks a right-or-down path from the top-left cell to the bottom-right cell, and the goal is the fewest paths covering every flower.
Level

Hard8 of 10

Topics
Graph, Combinatorics, Greedy, Sorting
Solved
No attempts yet

Problem

A field of pink flowers is divided into NN rows and MM columns of one square meter cells. The cell in row ii from the top and column jj from the left holds aija_{ij} flowers.

Every morning a group of rabbits comes to eat the flowers so that their fur turns pink. A rabbit starts at the top left cell and travels to the bottom right cell, moving one cell right or one cell down at a time. It never goes back to the left and never goes back up. Whenever a rabbit enters a cell that still holds at least one flower, it picks exactly one flower there. It walks past a cell with no flowers left without picking anything.

You may choose the route of every rabbit. Find the smallest number of rabbits needed to pick every flower in the field.

Input

The first line contains the number of test cases TT (1≤T≤101 \le T \le 10).

The first line of each test case contains the number of rows and columns of the field, NN and MM (1<N,M≤16001 < N, M \le 1600).

Each of the next NN lines contains MM integers. The jj-th integer on the ii-th line is aija_{ij} (0≤aij≤1000 \le a_{ij} \le 100).

Output

For each test case, print the smallest number of rabbits needed to pick every flower, one answer per line.

Examples3

  1. Example 1

    Input
    3
3 4
4 4 0 0
0 4 4 0
0 0 4 4
2 4
0 0 0 4
4 0 0 0
4 4
2 3 1 4
4 3 2 1
2 3 4 1
2 1 4 3
    Expected output
    4
8
11

  2. Example 2

    Input
    2
2 2
0 0
0 0
3 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
    Expected output
    0
0

  3. Example 3

    Input
    3
2 2
100 100
100 100
2 2
0 100
100 0
2 2
100 0
0 100
    Expected output
    200
200
100