Vitaly and Advanced Useless Algorithms

题意翻译

有 $n$ 个任务，每个任务要在 $a_i$ 时刻前做完。（$a$ 升序） 有 $m$ 个计划，每个计划最多只能执行一次，每个计划由 $e_i$, $t_i$, $p_i$ 描述：如果执行了第 $i$ 个计划，那么 $t_i$ 时间后，任务 $e_i$ 会被完成 $p_i$ 的百分比。 输入 $T$ 组数据。 输出每组执行的计划个数 $k$，并按顺序输出执行的计划（若不行则输出 `-1`，若有多种方案输出其中一种即可）。

题目描述

Vitaly enrolled in the course Advanced Useless Algorithms. The course consists of $ n $ tasks. Vitaly calculated that he has $ a_i $ hours to do the task $ i $ from the day he enrolled in the course. That is, the deadline before the $ i $ -th task is $ a_i $ hours. The array $ a $ is sorted in ascending order, in other words, the job numbers correspond to the order in which the assignments are turned in. Vitaly does everything conscientiously, so he wants to complete each task by $ 100 $ percent, or more. Initially, his completion rate for each task is $ 0 $ percent. Vitaly has $ m $ training options, each option can be used not more than once. The $ i $ th option is characterized by three integers: $ e_i, t_i $ and $ p_i $ . If Vitaly uses the $ i $ th option, then after $ t_i $ hours (from the current moment) he will increase the progress of the task $ e_i $ by $ p_i $ percent. For example, let Vitaly have $ 3 $ of tasks to complete. Let the array $ a $ have the form: $ a = [5, 7, 8] $ . Suppose Vitaly has $ 5 $ of options: $ [e_1=1, t_1=1, p_1=30] $ , $ [e_2=2, t_2=3, p_2=50] $ , $ [e_3=2, t_3=3, p_3=100] $ , $ [e_4=1, t_4=1, p_4=80] $ , $ [e_5=3, t_5=3, p_5=100] $ . Then, if Vitaly prepares in the following way, he will be able to complete everything in time: - Vitaly chooses the $ 4 $ -th option. Then in $ 1 $ hour, he will complete the $ 1 $ -st task at $ 80 $ percent. He still has $ 4 $ hours left before the deadline for the $ 1 $ -st task. - Vitaly chooses the $ 3 $ -rd option. Then in $ 3 $ hours, he will complete the $ 2 $ -nd task in its entirety. He has another $ 1 $ hour left before the deadline for the $ 1 $ -st task and $ 4 $ hours left before the deadline for the $ 3 $ -rd task. - Vitaly chooses the $ 1 $ -st option. Then after $ 1 $ hour, he will complete the $ 1 $ -st task for $ 110 $ percent, which means that he will complete the $ 1 $ -st task just in time for the deadline. - Vitaly chooses the $ 5 $ -th option. He will complete the $ 3 $ -rd task for $ 2 $ hours, and after another $ 1 $ hour, Vitaly will complete the $ 3 $ -rd task in its entirety. Thus, Vitaly has managed to complete the course completely and on time, using the $ 4 $ options. Help Vitaly — print the options for Vitaly to complete the tasks in the correct order. Please note: each option can be used not more than once. If there are several possible answers, it is allowed to output any of them.

输入输出格式

输入格式

The first line of input data contains an integer $ T $ ( $ 1 \le T \le 10^4 $ ) —the number of input test cases in the test. The descriptions of the input test case follow. The first line of each test case description contains two integers $ n $ and $ m $ ( $ 1 \le n,m \le 10^5 $ ) —the number of jobs and the number of training options, respectively. The next line contains $ n $ numbers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the time before the deadline of job $ i $ . The array values — are non-decreasing, that is $ a_1 \le a_2 \le \dots \le a_n $ . The following $ m $ lines contain triples of numbers $ e_i, t_i, p_i $ ( $ 1 \le e_i \le n $ , $ 1 \le t_i \le 10^9 $ , $ 1 \le p_i \le 100 $ ) — if Vitaly chooses this option, then after $ t_i $ hours he will increase the progress of the task $ e_i $ by $ p_i $ percent. The options are numbered from $ 1 $ to $ m $ in order in the input data. It is guaranteed that the sum of $ n+m $ on all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print on the first line the number $ k $ , meaning that for $ k $ of options, Vitaly will be able to complete each task by $ 100 $ percent or more on time. The options should not be repeated. Or print -1 if Vitaly is unable to complete all tasks in time. If there is an answer, on the next line print $ k $ of different integers from $ 1 $ to $ m $ — the numbers of the options in the order you want. If there is more than one answer, it is allowed to print any of them.

输入输出样例

输入样例 #1

5
3 5
5 7 8
1 1 30
2 3 50
2 3 100
1 1 80
3 3 100
1 5
51
1 36 91
1 8 40
1 42 83
1 3 45
1 13 40
2 9
9 20
2 8 64
2 7 64
1 20 56
2 8 76
2 20 48
1 2 89
1 3 38
2 18 66
1 7 51
3 2
7 18 33
1 5 80
3 4 37
2 5
569452312 703565975
1 928391659 66
1 915310 82
2 87017081 92
1 415310 54
2 567745964 82

输出样例 #1

4
1 4 3 5 
3
2 4 5 
4
6 7 1 2 
-1
4
2 4 3 5

输入样例 #2

3
3 9
20 31 40
1 9 64
3 17 100
3 9 59
3 18 57
3 20 49
2 20 82
2 14 95
1 8 75
2 16 67
2 6
20 36
2 2 66
2 20 93
1 3 46
1 10 64
2 8 49
2 18 40
1 1
1000000000
1 1000000000 100

输出样例 #2

-1
4
3 4 1 5 
1
1