该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

我宁愿留在你方圆几里

Description

在上上上上上上个礼拜，小马和她的队友 \(yjj\)，\(pjj\) 参加了 \(ICPC\) 上海站，在第一天热身赛的时候 \(yjj\) 和 \(pjj\) 光速解决掉了 \(A,\ B\) 两题，第三题是个计算几何，小马身为队伍里面的计算几何选手，看了许久题目，看了一眼榜，决定带着另外两个队友一起摸鱼，\(yjj\) 和 \(pjj\) 虽然无奈，但是由于不会计算几何也只能跟着小马一起摸鱼。

然后她们三个决定开始玩一种叫做猜数字的游戏。

游戏的大概规则是：每次由电脑随机生成一个 \([1, \ 10000]\) 之间的数字，以小马，\(yjj\)，\(pjj\) 顺时针的顺序猜数字，每次程序会告诉你猜的数字和目标数的大小关系并且根据猜的数字缩小区间，如果有人输入了区间以外的数字，会被判为不合法，需要那个人重新数字并且不合法的输入不会算一次游戏轮数（例如目标数字为 \(560\)，一开始的合法猜数字区间为 \([1, \ 10000]\)，猜数字 \(500\)，下一个人猜数字的合法区间为 \([501, \ 10000]\)，而猜数字 \(10^9\) 则是不合法的），最后猜中那个数字的人会得到这次游戏轮数所对应数字的分数。小马，\(yjj\)，\(pjj\) 所有人都不会采取游戏策略（可以理解为想到什么数字就会猜什么数字）。这个游戏一共会进行 \(n\) 次，第一次游戏第一次猜的人是小马，第 \(i\) 次 \((i \geq 2)\) 游戏第一次猜的人都是 \(i - 1\) 次游戏的获胜者。

现在给出 \(n\) 次游戏每次游戏的目标数和所有人的猜数字情况（不会给出哪个人猜的），请计算一下 \(n\) 次游戏之后最高分是多少（三个人初始分数都为 \(0\)）。

Format

Input

第一行输入一个正整数 \(n\)，表示游戏次数。
对于每次游戏，第一行输入两个正整数 \(m, \ k\)，表示这次游戏一共输入 \(m\) 个数字和这次游戏的目标数。
接下来 \(m\) 行，每行输入一个正整数，表示猜的数字

对于 \(100 \%\) 的数据，\(1 \leq n \leq 10^2\)，\(1 \leq m, \ k \leq 10^4\)，三人猜的数字 \(x\) 满足 \(-10^9 \leq x \leq 10^9\)

Output

输出共一行，\(n\) 次游戏之后最高分

Sample 1

Input

2
3 2
3
1
2
6 2
5
100
4
3
1
2

Output

5

Limitation

1s, 1024KiB for each test case.