题目描述

首先回顾一下田忌赛马这个古老的故事: 齐使者如梁，孙膑以刑徒阴见，说齐使。齐使以为奇，窃载与之齐。齐将田忌善而客待之。忌数与齐诸公子驰逐重射。孙子见其马足不甚相远，马有上、中、下辈。于是孙子谓田忌曰：“君弟重射，臣能令君胜。”田忌信然之，与王及诸公子逐射千金。及临质，孙子曰：“今以君之下驷与彼上驷，取君上驷与彼中驷，取君中驷与彼下驷。”既驰三辈毕，而田忌一不胜而再胜，卒得王千金。于是忌进孙子于威王。威王问兵法，遂以为师。

现在的问题： 田忌与齐王赛马，双方各有n匹马参赛（n

说明: 为了简单起见,保证2n匹马的速度均不相同。

输入格式

输入数据的第一行为一个正整数T（1

输出格式

针对每组测试数据输出一行数据,表示田忌比赛的最好结果是赢多少两黄金。

3
3
92 83 71
95 87 74
2
21 12
25 20
2
12 11
19 20

200
0
-400

提示

刀片地址：计算机1802 徐弘