Turtle restoring

The turtle wants to pass the rectangular table as quickly as possible from top left corner to bottom right corner along the route with the least losses.

Input

The first line contains two positive integers $n$ and $m(n,m\le 1000)$ — the size of the table. Each of the next $n$ lines contains $m$ integers — the description of the table, each cell contains the amount of acid in it (in milliliters).

The turtle can move only one cell down or right.

Output

Print in the first line the minimal possible turtle's damage. In the next lines print the cells coordinates along which the appropriate path runs. Print the coordinates in the order like they appear on the route.

Examples