401738: GYM100519 J JPEG is Awesome!

Anna and her husband Boris has finally got out to Prague. And now she is going on excursions with her new digital SLR camera every day. She is not very good at it and all of its functions, therefore she is only able to make photos and delete them. Since all excursions are made early in the morning and her husband Boris is very fond of Czech beer, she is going on excursions alone. She asks her husband to set needed photo quality an evening before excursions (the memory card is not very big, and she frequently needs to delete photos).

At the end of their trip, she found out that she had deleted many good photos during the trip, others were just plain bad, and some awesome photos were made in a bad quality since she tried to fit everything on a single memory card. If only she could have known everything in advance, her photo set would have been so much better!

You are about to research this topic together with Boris. It is known that their trip took K days, the memory card in their camera contains L units of memory, and every photo in RAW mode takes D memory.

For each day, it is known how much photos Anna made and the awesomeness factor Q_i, j of each photo. If Boris sets photo quality for the i-th day to α_i (0 ≤ α_i ≤ 1), then each photo on that day takes D·α_i memory (due to modern characteristics of memory used in their camera, this number can be non-integer), however the awesomeness factor of each photo is also multiplied by α_i. The α_i coefficient is the same for all photos taken on the same day but could be different for different days. It is also allowed to delete any photos at any time.

You are to find out the maximum possible awesomeness of the final set of photos. The awesomeness of the set of photos is the sum of awesomeness factors of each non-deleted photo.

The first line of input contains three integers K, L and D (1 ≤ K ≤ 10⁶, 1 ≤ L, D ≤ 10⁹).

The next K lines contain the descriptions of days. The first integer on a line is N_I, the number of photos taken on i-th day (1 ≤ N_i ≤ 10⁶). The next N_i integers Q_i, j are the awesomeness factors of the photos made on that day in the order they were taken (1 ≤ Q_i, j ≤ 10⁹). The sum of all N_i is less than or equal to one million.

The first line of output should contain the answer to the problem. If the answer is integer, output that integer, otherwise output the answer in the form "r + p / q" (without quotes and with single spaces before and after the "+" sign) where r, p and q are non-negative integers such that 0 < p < q and p and q are relatively prime.

It is guaranteed that the answer is always a rational number.

2 8 3
2 9 6
2 8 7

21 + 1/2

1 7 2
7 1 10 1 100 1 10 1

120