Problem1320--#2196. 「SDOI2014」Lis

1320: #2196. 「SDOI2014」Lis

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

给定序列 AAA,序列中的每一项 AiA_iAi 有删除代价 BiB_iBi 和附加属性 CiC_iCi

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

输入格式

输入包含多组数据。

输入的第一行包含整数 TTT,表示数据组数。
接下来 4T4T4T 行描述每组数据。
每组数据的第一行包含一个整数 NNN,表示 AAA 的项数,接下来三行,每行 NNN 个整数 A1,…,An, B1,…,Bn, C1,…,CnA_1,\ldots, A_n,\ B_1,\ldots,B_n,\ C_1,\ldots,C_nA1,,An, B1,,Bn, C1,,Cn

输出格式

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

样例

样例输入

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), (A1,A6), (A2,A3,A4,A5) 等都是合法的方案,但 (A2,A3,A6)(A_2, A_3, A_6)(A2,A3,A6) 对应的 CCC 值的字典序最小。

数据范围与提示

对于所有的数据,1≤N≤700, T≤5, 1≤Ai,Bi,Ci≤1091 \leq N \leq 700,\ T \leq 5,\ 1 \leq A_i, B_i, C_i \leq 10^91N700, T5, 1Ai,Bi,Ci109,且 CiC_iCi 两两不同。

Source/Category