#P18687. Canvas
Canvas
Canvas
有一个长度为 的序列,最初所有元素均为 。还有 次操作:第 次操作会将序列中第 个元素的值改为 ,同时将第 个元素的值改为 。每次操作都必须恰好执行一次。
请找出执行这些操作的最优顺序,使所有操作执行完毕后,序列中所有元素的和最大。
输入格式
输入包含多组测试用例。第一行包含一个整数 ,表示测试用例数。
对于每个测试用例:
第一行包含两个整数 (),分别表示序列长度和操作次数。
接下来 行,第 行包含四个整数 (,),表示第 次操作。
保证整个输入中所有测试用例的 之和不超过 ,所有测试用例的 之和也不超过 。
输出格式
对于每个测试用例,首先输出一行,包含一个整数,表示所有操作执行完毕后,序列中所有元素之和的最大值。
然后输出一行,包含 个用空格分隔的整数 ,表示最优的操作执行顺序,其中 是第 个执行的操作的编号。 到 中的每个整数都必须恰好出现一次。
如果存在多个合法答案,输出任意一个即可。
样例 1 输入
2
4 4
1 1 2 2
3 2 4 1
1 2 3 2
2 1 4 1
4 2
3 2 4 1
1 2 3 1
样例 1 输出
7
4 1 3 2
5
2 1
样例说明
对于第一组测试用例,按照 的顺序执行操作后,序列变为 ,所有元素的和为 。
对于第二组测试用例,按照 的顺序执行操作后,序列变为 ,所有元素的和为 。