#2196. 「SDOI2014」Lis

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定序列 AA,序列中的每一项 AiA_i 有删除代价 BiB_i 和附加属性 CiC_i

请删除若干项,使得 AA 的最长上升子序列长度减少至少 11,且付出的代价之和最小,并输出方案。
如果有多种方案,请输出将删去项的附加属性排序之后,字典序最小的一种。

输入格式

输入包含多组数据。

输入的第一行包含整数 TT,表示数据组数。
接下来 4T4T 行描述每组数据。
每组数据的第一行包含一个整数 NN,表示 AA 的项数,接下来三行,每行 NN 个整数 A1,,An, B1,,Bn, C1,,CnA_1,\ldots, A_n,\ B_1,\ldots,B_n,\ C_1,\ldots,C_n

输出格式

对每组数据,输出两行。
第一行包含两个整数 SSMM,依次表示删去项的代价和与数量;
接下来一行 MM 个整数,表示删去项在 AA 中的位置,按升序输出。

样例

样例输入

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

样例输出

4 3
2 3 6

样例解释

删去 (A2,A3,A6), (A1,A6), (A2,A3,A4,A5)(A_2, A_3, A_6),\ (A_1, A_6),\ (A_2, A_3, A_4, A_5) 等都是合法的方案,但 (A2,A3,A6)(A_2, A_3, A_6) 对应的 CC 值的字典序最小。

数据范围与提示

对于所有的数据,1N700, T5, 1Ai,Bi,Ci1091 \leq N \leq 700,\ T \leq 5,\ 1 \leq A_i, B_i, C_i \leq 10^9,且 CiC_i 两两不同。