Dystopian Land of Fives Part 3: A Portal To A Magical Land

For a long time, Brooke has been seeking a special portal to escape the dystopia on her land. After searching and being on the run for several years, she has finally found the portal. However, for the portal to work she has to solve the required problem on its keypad.

The keypad consists of ~n~ lines of integers. Each line ~L_i~ where ~1 \leq i \leq n~ consists of ~m~ integers. There are two rules for picking the right integer from each line:

1. For every line ~L_i~ where ~i~ is even, pick the highest integer from that line.
2. For every line ~L_i~ where ~i~ is odd, pick the lowest integer from that line.

The final result should be the sum of all the integers picked from each line.

Brooke is nervous and does not want to get this wrong. She needs your help to write a program which will pick the right numbers according to the rules and add them accordingly.

Input

The first line of input consists of two integers ~n\ (1 \leq n \leq 1000)~ and ~m\ (1 \leq m \leq 500)~.

The next ~n~ lines consist of ~m~ integers ~a_1, a_2, ... , a_m\ (-1000 \leq a_j \leq 1000)~.

Output

Print the sum of integers picked from each line.

Examples

Input 1

3 5
3 10 2 5 5
2 -1 3 4 -5
10 15 100 2 -2

Output 1

4

Explanation

According to the rules, pick 2, 4, -2 and add them together.