園遊會的預算表

題目敘述

校慶園遊會有 n 個班級，每個班級各提出若干種攤位方案。第 i 班有 m_i 種方案，第 j 種方案需要經費 c_i,j，可以帶來人氣值 p_i,j。

每個班級最多只能採用一種方案，也可以不採用任何方案。所有被採用方案的經費總和不可以超過學生會的預算 B（剛好等於 B 可以）。

請求出人氣值總和的最大值；如果有多種選法都能達到這個最大值，再求其中經費總和最小的是多少。

輸入格式

第一行有兩個整數 n、B。

接下來 n 行，第 i 行先是整數 m_i，之後依序是 m_i 組 c_i,j p_i,j，全部以空白分隔。

輸出格式

輸出一行兩個整數，以空白分隔：最大的人氣值總和，以及達到該人氣值所需的最小經費總和。若一個方案都不採用，輸出 0 0。

限制

• 1 ≤ n ≤ 100
• 1 ≤ m_i ≤ 20
• 1 ≤ c_i,j ≤ 10⁹
• 1 ≤ p_i,j ≤ 100
• 0 ≤ B ≤ 10¹⁵

子題配分

1. （15 分）n ≤ 8，m_i ≤ 3。
2. （25 分）B ≤ 20000。
3. （60 分）無額外限制。

範例

範例 1

輸入

3 9
2 4 5 6 8
1 5 6
2 3 2 9 10

輸出

11 9

範例 2

輸入

2 100
2 10 5 20 9
1 30 4

輸出

13 50

說明

範例 1 的預算為 9。第 1 班可選（經費 4，人氣 5）或（6，8），第 2 班可選（5，6），第 3 班可選（3，2）或（9，10）。

選第 1 班的（4，5）加上第 2 班的（5，6），經費 9 剛好等於預算，人氣值 11。其他選法的人氣值最多是 10，例如第 1 班（6，8）加第 3 班（3，2），所以答案是 11 9。

範例

範例 1

3 9
2 4 5 6 8
1 5 6
2 3 2 9 10

11 9

預算 9。選第 1 班的（4，5）和第 2 班的（5，6），經費剛好 9，人氣值 11。其他選法最多 10，所以答案是 11 9。

範例 2

2 100
2 10 5 20 9
1 30 4

13 50

預算很充裕，但第 1 班只能選一個方案。選（20，9）和第 2 班的（30，4），人氣值 13，經費 50。若第 1 班兩個都選會得到 18，那是不合法的。