Description

A公司最近招收了一批人数为n的新员工(编号为1...n)，要将他们全部分配给m个部门。

m个部门头头面试员工之后，都已有了心中人选。但是每个部门头头对自己的人选还有不同的满意程度，满意程度越高，则越满意(1<=亲密度<=20000)。每个部门最多可招收k个员工。要求计算出n个员工都被分配之后，最低满意度的最大值(即n个数的最小值要尽量大)。

Input

每组数据有m+1行。第一行为n,m,k(1<=n<=200,1<=m<=15,1<=k<=30)。 下面m行表示m个部门头头的心中人选，格式为:p num1,c1 num2,c2.....nump,cp。 p表示心中人选个数，后面p对数据代表新员工编号和亲密度。

Output

输出分配完后最小满意度的最大值。

Sample

Input

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

Output

5

Source: catlwwy