n, m = map(int, input().split())
profit = []
for _ in range(n):
profit.append([0]+list(map(int, input().split())))
dp = [0] * (m+1)
assign = [[0] * n for _ in range(m+1)]
for i in range(n):
for j in range(m, 0, -1):
for k in range(j, 0, -1):
if dp[j-k] + profit[i][k] > dp[j]:
dp[j] = dp[j-k] + profit[i][k]
assign[j] = assign[j-k].copy()
assign[j][i] = k
print(dp[m])
for i in range(n):
print(i+1, assign[m][i])