LQDNTDIV1

Có lọ hoa sắp thẳng hàng và  bó hoa được đánh số thứ tự từ nhỏ đến lớn. Cần cắm hết  bó hoa trên vào  lọ sao cho hoa có số thứ tự nhỏ phải đứng trước hoa có số thứ tự lớn. Giá trị thẩm mỹ tương ứng khi cắm hoa i vào lọ thứ j là  Hãy tìm 1 cách cắm sao cho tổng giá trị thẫm mỹ là lớn nhất. Chú ý rằng mỗi bó hoa chỉ được cắm vào 1 lọ và mỗi lọ cũng chỉ cắm được nhiều nhất là 1 bó hoa. Giới hạn: 1<=n,k<=1000 ; -100<=v_ij<=100

Input

Dòng đầu ghi hai số nguyên n, k

Trong k dòng kế tiếp, mỗi dòng ghi n số nguyên mô tả bảng v

Output

Dòng đầu ghi một số nguyên duy nhất là tổng giá trị thẩm mỹ của cách cắm tối ưu. Nếu không tồn tại cách cắm thỏa yêu cầu, ghi -1

Trong k dòng kế tiếp, dòng thứ i ghi hai số i, p cho biết hoa thứ i được cắm vào lọ p. 

Example

Input:
5 4
3 -2  1 -1  3
2 -3  1 -5  3
-2 0  2  4  1
1  1 -1  -3 4.
Output:
12
1 1
2 3
3 4
4 5