给定序列 A,序列中的每一项 A_i 有删除代价 B_i 和附加属性 C_i。请删除若干项,使得 A 的最长上升子序列长度减少至少 1,且付出的代价之和最小,并输出方案。
如果有多种方案,请输出将删去项的附加属性排序之后,字典序最小的一种。
输入包含多组数据。
输入的第一行包含整数 T,表示数据组数。接下来 4T 行描述每组数据。
每组数据的第一行包含一个整数 N,表示 A 的项数。
接下来三行,每行 N 个整数 A_1\sim A_n,B_1\sim B_n,C_1\sim C_n,满足 1\le A_i,B_i,C_i \le 10^9,且 C_i 两两不同。
对每组数据,输出两行。第一行包含两个整数 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 值的字典序最小。
对于 100\% 的数据,1\le N\le 700,1\le T\le 5。
山东省选