Соревнование по программированию

시간 제한2초메모리 제한1024 MB

요약

각자 아는 문제를 L분에 하나씩 푸는 N명이 T분 안에 최대 몇 문제를 풀 수 있는지, 그때 최소 총 패널티가 얼마인지 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

Чтобы Эдвард меньше охотился на невинных существ, Белла решила найти ему какое-нибудь увлекательное занятие. Всем известно, что нет ничего более увлекательного, чем участвовать в командных соревнованиях по программированию. Оказалось, что для участия в соревновании нужна команда из $N$ человек, поэтому Эдвард позвал своих знакомых вампиров, а Белла --– школьниц. Таким образом, в команде оказалось ровно $N$ участников.

Соревнование идет ровно $T$ минут. В отличие от обычных соревнований, каждому участнику полагается компьютер, на котором он может работать независимо от сокомандников. Командам предложено решить $M$ задач. Про каждую из задач Эдварду известно, какие члены его команды могут ее решить. Так же ему известно, что на решение любой задачи любому члену команды, который умеет ее решать, потребуется ровно $L$ минут, чтобы ее решить.

Штраф за задачу --– время, прошедшее от начала соревнования, до того момента, как ее решили. Штраф команды --– сумма штрафов за все задачи, которые она решила. Нерешенные задачи никак не влияют на штраф.

Эдварду интересно, какое максимальное количество задач сможет решить его команда при оптимальном распределении заданий между членами команды. Если существует несколько способов это сделать, Эдвард хотел бы минимизировать штраф.

입력

Первая строка входного файла содержит числа $N$ , $M$ , $T$ и $L$ ( $1\le N,M\le 100$ , $1\le L\le T\le 10000$ ) --- количество членов команды, количество задач, продолжительность соревнования в минутах и время в минутах, за которое один участник способен решить одну задачу соответственно.

Следующие $N$ строк содержат описание каждого участника: сначала идет число $K$ ( $0\le K \le M$ ) --- количество задач, которые умеет решать участник, затем $K$ различных чисел --- номера этих задач. Задачи нумеруются натуральными числами начиная с единицы.

출력

Выведите два числа --- максимальное количество задач, которые успеет решить команда Эдварда и Беллы, и минимальный штраф, который при этом может быть достигнут.

힌트

Первый участник решает первую задачу, второй вторую, а третий --- последние две. Таким образом, суммарный штраф --- 2+2+2+4=10.

예제1

예제 1
입력
```
3 4 10 2
1 1 
2 1 2
2 3 4
```
예상 출력
```
4 10
```