Lab scheduling

The campus lab is available for D_max consecutive days. Those days are numbered by integers 0, 1, ..., D_max−1. We will call these days calendar days.
There is some number of experiments which scientists want to conduct using the lab.
The lab is in high demand and the experiments have to be carefully chosen.
No experiment can be conducted two or more times in the lab.
Each experiment is assigned a value, the so called gain of the experiment.
The task is to choose a set of experiments and schedule them in the lab in such way that the total gain is maximized, and moreover the total number of days in which the lab is occupied is also maximized.

The important feature of the lab is that on any day it can be used for at most one experiment. No two experiments can be conducted in the lab on the same calendar day.

Fortunately, each experiment is internally well organized and between its start and its completion it has to occupy the lab only on a few days, not necessarily consecutive. Those days are called active days of the experiment. Active days of an experiment are described by a strictly increasing sequence of integers in which each entry denotes the relative number of days between the particular active day and the experiment start day.
For example, an experiment with active days sequence (0, 2, 5, 11) will occupy the lab on exactly four days. Those will be the start day of the experiment and additional three days which come 2, 5, 11 days, respectively, after the experiment start day.
Each experiment active days sequence starts with 0. It only reflects the fact that each experiment starts in the lab.
Note that the active days sequence does not specify on which calendar days will be the experiment conducted in the lab. This specification is left to the so called experiment schedule.

An experiment schedule is a strictly increasing sequence of numbers derived from the experiment active days sequence. It specifies the calendar days in which the experiment will occupy the lab. The first schedule entry is a nonnegative integer m specifying the calendar day on which the experiment will actually begin. Each next schedule entry specifies another calendar day which number is equal to the corresponding active days sequence entry increased by m.
For example, (0, 2, 5, 11), (1, 3, 6, 12), (4, 6, 9, 15) are three possible schedules of an experiment with active days sequence equal to (0, 2, 5, 11).

Two experiment schedules collide if there exist an entry with the same value in both schedules.
For example, let us consider the schedules of three different experiments: (1, 8, 17), (4, 5, 8, 10), (1, 2, 11, 17, 18).
The first experiment schedule collides with the second experiment schedule due to the value 8, and it collides with the third experiment due to the values 1 and 17. The second and the third experiment schedules do not collide.

A set of experiments is a feasible set if a schedule can be assigned to each experiment in the set in such way that both of the following holds:
   1. No two schedules collide.
   2. Each entry in the schedule of each set lies in interval [0, D_max−1].
The gain of a set of feasible experiments is the sum of gains of all experiments in the set.

Illustration

Let there be 5 experiments labeled A, B, C, D, E with respective active days sequences

A: (0, 1, 2, 5); B: (0, 4, 5, 6);  C: (0, 1); D: (0, 1); E: (0,1).

day           0  1  2  3  4  5  6  7  8  9 10
experiment    D  D  B  E  E  _  B  B  B  C  C

B: (6, 7);  C: (9, 10); D: (0, 1); E: (3, 4, 6, 7).

The task

You are given a list of gains and active days of a few experiments and a number of consecutive days in which the lab is available. Calculate the maximum gain of a feasible set of experiments which can be conducted in the lab according to the limitations specified above. Find also the maximum possible number of occupied days in the lab for all sets of experiments which attain the maximum gain.

Input

The first input line contains two integers N, D_max representing the number of experiments and the number of successive days in which the lab is available. Next, there are N pairs of lines, each describes one experiment. The first line in each pair specifies the number of active days of the experiment and the gain of the experiment. The second line in each pair contains the list of experiment active days sorted in increasing order.
All values on all lines are separated by spaces.
It holds 2 ≤ N ≤ 15, 4 ≤ D_max ≤ 50. All experiment gains are positive integers less than 10⁵.

Output

The output contains one text line with two integers G, D separated by space. G represents the maximum gain of a set of feasible experiments. D represents the maximum possible number of occupied days in the lab for a set of experiments which gain is G.

5 11
4 101
0 1 2 5
4 102
0 4 5 6
2 104
0 1
2 108
0 1
2 116
0 1

430 10

4 13
4 101
0 4 8 12
4 102
0 3 7 8
2 104
0 4
4 108
0 1 6 12

314 10

4 15
4 101
0 4 8 12
4 102
0 3 7 8
2 104
0 4
4 108
0 1 6 12

415 14

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set