芥川龙之介的河童

题目描述

为了增加守矢神社的信仰，八坂神奈子邀请河城荷取为神社修建御柱。一根御柱由若干楼层组成。

荷取的初始资金是 x 个黄瓜（对河童来说是一种非常宝贵的货币）。共有 n 根可供建造的御柱，编号为 1 到 n。每根御柱的建造相互独立、互不影响；目前还没有任何御柱开始建造。

为了建造第 i 根御柱的第 j 层，需要花费 a_{i,j} 个黄瓜；建造完成后，荷取会立即收到 b_{i,j} 个黄瓜，并加入她的预算中，可用于建造任何御柱的楼层。注意，同一根御柱的楼层必须按编号从小到大依次建造：必须先建好第 1 层，才能建造第 2 层，依此类推。

由于神奈子非常狡诈，并非所有合同都一定有利可图，甚至可能存在 a_{i,j} > b_{i,j} 的情况（即建造该层反而会亏损）。

荷取可以自由安排建造顺序：她可以在不同御柱之间任意切换，也可以在建造过程中穿插任意数量的其他合同。她不需要建造所有楼层，甚至可以完全不建造任何楼层。

荷取的目标是让其中一根御柱建得尽可能高。请你帮助荷取规划建造方案，求出她能让御柱达到的最大层数，以及能达到该层数的御柱中最小的编号。

每个测试包含多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 3×10^4），表示测试用例的数量。

每个测试用例的格式如下：

第一行包含两个整数 n 和 x（1 ≤ n ≤ 2×10^5，0 ≤ x ≤ 10^18）——御柱的数量和初始资金；
接下来是 n 根御柱的描述，第 i 根御柱的描述为：
- 第一行包含一个整数 m_i（1 ≤ m_i ≤ 2×10^5）——该御柱最多可建造的层数；
- 第二行包含 m_i 个整数 a_{i,1}, a_{i,2}, …, a_{i,m_i}——建造各层需要的花费；
- 第三行包含 m_i 个整数 b_{i,1}, b_{i,2}, …, b_{i,m_i}——建造各层后立即收到的黄瓜数。

其中 0 ≤ a_{i,j}, b_{i,j} ≤ 10^9。保证所有测试用例的 m_i 之和不超过 2×10^5。

对每个测试用例，输出一行两个整数：荷取能让御柱达到的最大层数 h，以及能达到层数 h 的御柱中最小的编号。

输入：

输出：

4 1
2 1

测试用例 1： 资金足够依次建造唯一一根御柱的全部 4 层，所以答案是 4 1。

测试用例 2： 可以先建造第 2 根御柱的第 1 层（花费 2，得到 4，净赚 2 个黄瓜），此时资金变为 5；再依次建造第 1 根御柱的两层（共花费 8，共得到 10，净赚 2），第 1 根御柱因此达到 2 层；第 2 根御柱最多只有 1 层，所以答案是 2 1。