Team Programming Contest

Bartie and his friends compete in a team programming contest. There are \(n\) contestants on each team and \(n\) computers available. The contest lasts \(t\) minutes, during which the team must solve \(m\) programming problems. A penalty is incurred for each problem solved, equal to the minute in which it was solved (i.e. if a problem is solved at minute \(s\), the penalty is \(s\)). The winner is the team that solves the most problems, with ties broken by smaller penalty.

Before the contest starts, Bartie examines the problems and knows exactly which teammate is capable of solving each problem. Every problem that a contestant is able to solve takes exactly \(r\) minutes of computer use. A contestant may solve multiple problems sequentially (each taking \(r\) minutes) but cannot work on more than one problem at the same time. Thus, a contestant can solve at most \(\left\lfloor \frac{t}{r} \right\rfloor\) problems during the contest.

Your task is to help him determine the best possible result for his team, and output an assignment of problems to team members that attains that result. The total penalty is computed as follows: if a contestant solves \(k\) problems then the finish times are \(r, 2r, \ldots, kr\) and the penalty sum for that contestant is \(r \times \frac{k(k+1)}{2}\). The overall penalty is the sum of the penalties for each contestant.

inputFormat

The first line of input contains four space-separated integers: \(n\), \(m\), \(t\), and \(r\). \(n\) is the number of contestants (and computers), \(m\) is the number of problems, \(t\) is the total contest time (in minutes), and \(r\) is the amount of time required to solve any problem.

The following \(n\) lines each contain a binary string of length \(m\). The \(j\)-th character on the \(i\)-th line is '1' if contestant \(i\) is able to solve problem \(j\) and '0' otherwise.

outputFormat

On the first line, output two space-separated integers: the maximum number of problems that can be solved and the minimum total penalty achieved by an assignment.

The second line should contain an integer \(k\) representing the number of assignments (this equals the number of solved problems). Each of the next \(k\) lines should contain three space-separated integers: the contestant index (1-indexed), the problem index (1-indexed), and the finish time (in minutes) when that contestant completes the problem.

sample

2 3 10 5
110
101

3 20
3
1 1 5
1 2 10
2 3 5