#2196. 「SDOI2014」Lis

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

题目描述

给定序列 A ,序列中的每一项 A_i 有删除代价 B_i 和附加属性 C_i

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

输入格式

输入包含多组数据。

输入的第一行包含整数 T ,表示数据组数。
接下来 4T 行描述每组数据。
每组数据的第一行包含一个整数 N ,表示 A 的项数,接下来三行,每行 N 个整数 A_1,\ldots, A_n,\ B_1,\ldots,B_n,\ C_1,\ldots,C_n

输出格式

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

样例

样例输入

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

样例解释

删去 (A_2, A_3, A_6),\ (A_1, A_6),\ (A_2, A_3, A_4, A_5) 等都是合法的方案,但 (A_2, A_3, A_6) 对应的 C 值的字典序最小。

数据范围与提示

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