← 返回题目列表

Codeforces · 1650/F

F. Vitaly 和高级无用算法

中文机器翻译题面 查看原题

Vitaly 参加了高级无用算法课程。该课程由 $$$n$$$ 任务组成。 Vitaly 计算出,从他报名课程之日起,他有 $$$a_i$$$ 小时来完成 $$$i$$$ 任务。也就是说,第 $$$i$$$ 个任务之前的截止日期是 $$$a_i$$$ 小时。数组 $$$a$$$ 按升序排序,换句话说,作业编号对应于作业提交的顺序。

Vitaly 做每件事都很认真,所以他希望以 $$$100$$$% 或更多的速度完成每项任务。最初,他每项任务的完成率为 $$$0$$$%。

Vitaly 有 $$$m$$$ 训练选项,每个选项只能使用一次。 $$$i$$$th 选项由三个整数表示:$$$e_i、t_i$$$ 和 $$$p_i$$$。如果 Vitaly 使用第 $$$i$$$ 选项,那么在 $$$t_i$$$ 小时后(从当前时刻开始),他会将任务 $$$e_i$$$ 的进度增加 $$$p_i$$$%。

例如,让 Vitaly 有 $$$3$$$ 的任务需要完成。令数组 $$$a$$$ 具有以下形式:$$$a = [5, 7, 8]$$$。假设 Vitaly 有 $$$5$$$ 个选项:$$$[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]$$$。

那么,如果维塔利按照以下方式做好准备,他就能及时完成一切:

- Vitaly 选择了第 $$$4$$$ 个选项。然后在 $$$1$$$ 小时内,他将以 $$$80$$$% 的速度完成 $$$1$$$-st 任务。距离第 $$$1$$$ 任务的截止日期还有 $$$4$$$ 小时。
- Vitaly 选择了 $$$3$$$-rd 选项。然后在 $$$3$$$ 小时内,他将完整完成第 $$$2$$$-nd 任务。距离第 $$$1$$$-st 任务的截止日期还有 $$$1$$$ 小时,距离第 $$$3$$$-rd 任务的截止日期还剩 $$$4$$$ 小时。
- Vitaly 选择了 $$$1$$$-st 选项。然后,在 $$$1$$$ 小时后,他将完成 $$$1$$$-st 任务,并获得 $$$110$$$%,这意味着他将在截止日期前及时完成 $$$1$$$-st 任务。
- Vitaly 选择了第 $$$5$$$ 个选项。他将在 $$$2$$$ 小时内完成 $$$3$$$-rd 任务,再过 $$$1$$$ 小时后,Vitaly 将完整完成 $$$3$$$-rd 任务。

因此,Vitaly 使用 $$$4$$$ 选项成功按时完整地完成了课程。

帮助 Vitaly — 打印 Vitaly 的选项,以按照正确的顺序完成任务。请注意:每个选项只能使用一次。如果有多个可能的答案,则允许输出其中任何一个。

输入

输入数据的第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 10^4$$$)——测试中输入测试用例的数量。

输入测试用例的描述如下。

每个测试用例描述的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n,m \le 10^5$$$) - 分别是作业数量和训练选项数量。

下一行包含 $$$n$$$ 数字 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 作业 $$$i$$$ 截止日期之前的时间。数组值是非递减的,即 $$$a_1 \le a_2 \le \dots \le a_n$$$。

以下 $$$m$$$ 行包含数字三元组 $$$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$$$) — 如果 Vitaly 选择此选项,则在$$$t_i$$$ 小时,他会将任务 $$$e_i$$$ 的进度提高 $$$p_i$$$%。选项在输入数据中按顺序从 $$$1$$$ 到 $$$m$$$ 编号。

保证所有测试用例的 $$$n+m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在第一行打印数字 $$$k$$$,这意味着对于 $$$k$$$ 选项,Vitaly 将能够按 $$$100$$$ 或更多百分比按时完成每项任务。选项不应重复。或者如果 Vitaly 无法及时完成所有任务,则打印 -1。

如果有答案,请在下一行打印从 $$$1$$$ 到 $$$m$$$ 的不同整数 $$$k$$$ — 按您想要的顺序排列的选项编号。如果有多个答案,则允许打印其中任何一个。

示例

输入 #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