항공권 가격 정하기

항공권 가격은 주마다 크게 오르내리고, 여행자는 그 움직임을 예측하지 못한다. 일찍 표를 산 사람은 며칠 뒤 가격이 떨어지는 것을 보고, 기다린 사람은 결제 직전에 가격이 오르는 것을 본다. 결국 웃는 쪽은 항공사뿐이다.

가격이 흔들리는 데에는 나름의 규칙이 있다. 항공사는 남은 좌석 수와 출발까지 남은 주 수를 보고 그때그때 가격을 정한다. 남은 좌석이 얼마 없으면 출발 직전 몇 주까지 비싼 가격을 유지하다가, 빈자리를 채우려고 가격을 내리기도 한다. 항공사의 목표는 한 편에서 얻는 수익을 최대로 만드는 것이다.

International Contrived Pricing Corporation은 주마다 항공권 가격을 정하는 일을 맡기려고 당신을 고용했다. 항공사는 과거 자료를 분석해서, 출발까지 몇 주가 남았을 때 어떤 가격이면 표가 몇 장 팔리는지 꽤 정확하게 추정한다. 남은 좌석 수와 출발까지 남은 주 수가 주어질 때, 이번 주부터 출발하는 주까지 얻는 총수익이 최대가 되도록 이번 주 가격을 정하라.

팔리는 표의 수는 추정치와 정확히 같다고 가정한다. 다만 남은 좌석이 추정치보다 적으면 남은 좌석이 모두 팔린다. 이후의 주에는 항상 최적의 가격을 고른다고 가정한다.

가격이 높다고 해서 표가 반드시 덜 팔리지는 않는다. 가격이 더 오를까 봐 걱정한 여행자가 몰려서, 비싼 가격에 오히려 표가 더 많이 팔리기도 한다.

입력은 항공편 하나를 나타낸다. 첫 줄에 남은 좌석 수 $N$과 출발까지 남은 주 수 $W$가 주어진다 ($0 < N \le 300$, $0 \le W \le 52$).

다음 $W + 1$개의 줄에는 남은 주 수가 $W, W - 1, \dots, 0$일 때의 추정치가 순서대로 주어진다. 남은 주 수가 $0$인 줄이 마지막 주다. 각 줄은 그 주에 고려할 가격의 개수 $K$로 시작한다 ($0 < K \le 100$). 이어서 가격 $p_1, \dots, p_K$가 달러 단위로 주어지고 ($0 < p_1 < \cdots < p_K < 1000$), 그 뒤에 정수 $s_1, \dots, s_K$가 주어진다 ($0 \le s_i \le N$). $s_i$는 가격이 $p_i$일 때 팔리는 표의 수다.

첫 줄에 이번 주부터 출발하는 주까지 항공사가 얻을 수 있는 최대 총수익을 출력한다. 둘째 줄에는 그 수익을 얻으려고 이번 주, 즉 출발까지 $W$주 남은 주에 정해야 할 가격을 출력한다.

최대 수익을 얻는 가격 조합이 여러 가지면 $W$주 차 가격 중 가장 작은 값을 출력한다.