Server Time:

User's AC Ratio in this contest

NaN% (0/0)

Submission's AC Ratio in this contest

NaN% (0/0)

Description

在台灣,發(領)紅包是個再平常不過的事情了。
快要過年了,小孩們這次非常期待領紅包,這樣就可以去買電腦,買玩具:)
不過厭倦單純發紅包的大人們,今年想出了一個特別的遊戲,讓小孩們在領紅包時也順便玩遊戲。
大人們設計了一個 $m\times n$ 矩陣,並且在矩陣的某一些格子放上紅包,並且每個紅包都有至少一塊錢ww
現在大人們跟小孩們會玩遊戲,且他們每一回合都有機會拿走矩陣上的紅包。

每一回合拿紅包的規則如下:
一、從大人們先開始拿。大人一次可以拿很多個紅包,而且在一回合中可以拿很多次。
大人們能拿取紅包是有條件的,如果大人要拿走第 $i$ 行第 $j$ 列的紅包,必須要滿足其中至少一個以下條件:

  • 第 $i$ 行只剩下該紅包
  • 第 $j$ 列只剩下該紅包

二、大人拿完紅包之後輪到小孩。小孩們可以派出一人拿矩陣中的一個紅包,且拿走的紅包沒有條件限制。
遊戲持續到紅包都拿完為止。

這個局勢顯然對小孩比較有利,所以當大人們可以拿走紅包的時候,有能拿的紅包就會拿,不會留情的。
小明是其中一個小孩,他的超能力是透視眼,可以直接看穿每個紅包裡有多少錢。
可惜小孩們的數學都不好,需要你的求助,請寫個程式幫小孩們拿到盡可能多的錢。

Input Format

第一行有 $n,m$ $(1\leq n,m \leq 10^3)$,表示矩陣的大小。
接下來有 $n$ 行,每一行有 $m$ 個數字,代表大人們安排的矩陣。
第 $i$ 行第 $j$ 列的紅包有數字 $A_i$ $(0\leq A_i \leq 10^3)$ ,如果 $A_i$ 是 $0$ 代表該位置沒有紅包,反之該位置就有 $A_i$ 元的紅包。

Output Format

輸出一個數字,代表小孩最多可以拿多少錢。

Sample Input 1

2 3
2 0 5
9 7 1

Sample Output 1

9

Sample Input 2

3 4
0 2 7 5
5 3 8 10
4 5 0 2

Sample Output 2

28

Sample Input 3

6 8
9 8 4 7 10 4 4 9
4 9 7 4 10 7 8 0
0 1 3 3 10 10 6 6
10 3 8 6 10 7 4 3
1 1 9 6 0 4 6 0
8 4 5 4 7 10 1 3

Sample Output 3

225

Hints

在 Sample 1 中,因為第二直行只有一個紅包,大人們可以先把它拿走。然後輪到小孩。
小孩只能拿一個,所以選最大的 $9$,然後紅包在下一回合中被大人拿光。
貪心的大人們(X

Problem Source

Subtasks

No. Testdata Range Score
1 0~23 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1
23 1000 65536 65536 1