1650F - Vitaly and Advanced Useless Algorithms - CodeForces Solution

import io, os, sys, math, bisect, collections, string


input = lambda : sys.stdin.readline().strip()


def solve():
    (n,m) = map(int, input().split())
    a = list(map(int, input().split()))
    trainings_by_tasks = [[] for _ in range(n)]
    for i in range(m):
        (e,t,p) = map(int, input().split())
        e -= 1
        trainings_by_tasks[e].append((t,p,i+1))
    task_times = []
    for trainings in trainings_by_tasks:
        dp = [(None,[]) for i in range(101)]
        dp[0] = (0,[])
        for (t,p,training_index) in trainings:
            for i in range(100,-1,-1):
                time = dp[i][0]
                if time is None:
                    continue
                next = min(i + p,100)
                next_time = time + t
                if dp[next][0] is None or next_time < dp[next][0]:
                    dp[next] = (next_time, dp[i][1] + [training_index])
        if dp[100][0] is None:
            print(-1)
            return
        task_times.append((dp[100][0], dp[100][1]))
    curr_time = 0
    ans = 0
    for (i,(time,sequence)) in enumerate(task_times):
        curr_time += time
        deadline = a[i]
        ans += len(sequence)
        if curr_time > deadline:
            print(-1)
            return
    print(ans)
    for time,sequence in task_times:
        print(*sequence,end=" ")
    print()


for t in range(int(input())):
    solve()