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

题目背景

本题出题人：@241240027汪林辰

$\quad$yummy最近沉迷《骑马与砍杀》。可惜他的钱包比萨兰德苏丹国的沙漠还要贫瘠，连最破旧的皮甲都买不起的他。因此，他只能硬着头皮去找土豪朋友哈劳斯国王借钱。

$\quad$"借钱？小事一桩！"国王晃着纯金酒杯漫不经心地说，"不过要是亏了本，你就得来我的竞技场当'常驻嘉宾'了~"

$\quad$yummy盘算着用这笔钱从帕拉汶跑商到库丹(下图仅供参考，实际问题以形式化描述为准)。但各城物价就像战场局势一样瞬息万变——罗多克的盐上午可能贱如尘土，下午就能贵比黄金。胆小的yummy实在拿不准这趟买卖能不能赚钱，迟迟不敢接下哈劳斯的贷款。

$\quad$请你编写一个程序，帮yummy计算出这趟商路能获得的最大利润，好让他决定要不要接下国王的贷款。

形式化描述

$\quad$给定 n 座城市（编号 1 ~ n）和 m 种商品（编号 1 ~ m）。每座城市有k个商贩，每个商贩出售一种商品并给出其对应的价格，除了出售以外，商贩还会收购与自己出售商品同种的商品。

$\quad$需要特别注意的是：每个商贩出售的商品种类可能相同，但价格可能不同。

$\quad$为了大幅降低难度，我们特别规定：

$\quad$• 跑商路线固定为从城市 $1$ 到城市 $n$

$\quad$• 对于每种商品，只有当前城市存在对应商贩你才能（但不强制）买卖

$\quad$• 每种商品在同一城市中只能执行买或卖的其中一种操作，不能在同一城市对同种商品执行两种操作

$\quad$• 商贩的出售价格和收购价格相同

$\quad$• 同一城市中同种商品只能被购买一次

$\quad$• 卖出某种商品时必须卖出持有的全部该种商品，且后续不能再买入该种商品

$\quad$• 初始资金无限（哈劳斯的大手）

输入格式

$\quad$第一行为整数 $T$（测试用例数量），接下来有 $T$ 个测试用例。 每个测试用例的格式如下：

$\quad$第一行：两个正整数 $n$ 和 $m$（$n^2 \times m \leq 10^6, n \leq 10^3, m \leq 10^3$），表示城市数量和商品种类数

随后 $n$ 行数据,每行对应一座城市：

$\quad$• 首个整数 $k$ $(0 \leq k \leq 10^3)$ 表示该城市的商品个数

$\quad$• 接下来 $k$ 对整数 $id$ $(1 \leq id \leq m)$和 $cost$，表示每个商品的编号和单价

$\quad$题目保证 $\color{red}T \times n^2 \times m \leq 10^7$ $\quad$且所有中间计算结果和最终结果不超过 $10^{18}$

输出格式

$\quad$输出一个整数,表示可获得的最大利润。

样例

2
3 3
2 1 1 2 2
2 1 2 2 4
0
4 4
3 1 1 2 2 1 3
2 1 2 1 3 
3 1 1 3 1 4 1
2 1 4 4 2

3
9

样例解释

$\quad$第一组测试用例:

$\quad$最优策略为：在1号城市花 3元 买入 商品1 和 商品2，再在2号城市以 6元 的价格卖出 商品1 和 商品2，总利润为 3元。

$\quad$第二组测试用例：

$\quad$最优策略为：在1号城市花 1元 买入 商品1， 在2号城市花 2元 买入 商品1 在 3号城市以 2元 买入 商品1 和 商品4，在4号城市以 14元 卖出 商品1 和 商品4，总利润为 9元。

时空限制

c/c++ 2500ms, 256MB

其他语言 5000ms, 512MB