Chef is operating a slush machine. The machine produces slush drinks with $M$ flavors (numbered $1$ through $M$); for each valid $i$, the maximum number of drinks with flavour $i$ the machine can produce is $C_i$.
Chef expects $N$ customers to come buy slush drinks today. The customers are numbered $1$ through $N$ in the order in which they buy the drinks. For each valid $i$, the favorite flavour of the $i$-th customer is $D_i$ and this customer is willing to pay $F_i$ units of money for a drink with this flavour, or $B_i$ units of money for a drink with any other flavuor. Whenever a customer wants to buy a drink:
- if it is possible to sell this customer a drink with their favourite flavour, Chef must sell them a drink with this flavour
- otherwise, Chef must sell this customer a drink, but he may choose its flavour
Chef wants to make the maximum possible profit. He is asking you to help him decide the flavours of the drinks he should sell to the customers in order to maximise the profit.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $M$.
- The second line contains $M$ space-separated integers $C_1, C_2, \ldots, C_M$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains three space-separated integers $D_i$, $F_i$ and $B_i$.

-----Output-----
For each test case, print two lines:
- The first of these lines should contain a single integer — the maximum profit.
- The second line should contain $N$ space-separated integers denoting the flavours of the drinks Chef should sell, in this order.
If there are multiple solutions, you may find any one.

-----Constraints-----
- $1 \le T \le 1,000$
- $2 \le N, M \le 10^5$
- $1 \le D_i \le M$ for each valid $i$
- $1 \le C_i \le N$ for each valid $i$
- $1 \le B_i < F_i \le 10^9$ for each valid $i$
- $C_1+C_2+\ldots+C_M \ge N$
- the sum of $N$ over all test cases does not exceed $10^6$
- the sum of $M$ over all test cases does not exceed $10^6$

-----Example Input-----
1
5 3
1 2 3
2 6 3
2 10 7
2 50 3
1 10 5
1 7 4

-----Example Output-----
33
2 2 3 1 3

Difficulty: interview

Starter code:

Solutions:
t=int(input())
for i in range(t):
 n,m=list(map(int,input().split()))
 l=[0]+list(map(int,input().split()))
 s=0
 c=1
 m1=[]
 for i in range(n):
  d,f,b=list(map(int,input().split()))
  if(l[d]>0):
   m1.append(d)
   s+=f
   l[d]-=1
  else:
   m1.append(0)
   s+=b
 for i in range(n):
  if(m1[i]==0):
   for j in range(c,m+1):
    if(l[j]>0):
     m1[i]=j
     l[j]-=1
     c=j
     break
 print(s)
 print(*m1)


t=int(input())
for i in range(t):
 n,m=list(map(int,input().split()))
 l=[0]+list(map(int,input().split()))
 s=0
 c=1
 m1=[]
 for i in range(n):
  d,f,b=list(map(int,input().split()))
  if(l[d]>0):
   m1.append(d)
   s+=f
   l[d]-=1
  else:
   m1.append(0)
   s+=b
 for i in range(n):
  if(m1[i]==0):
   for j in range(c,m+1):
    if(l[j]>0):
     m1[i]=j
     l[j]-=1
     c=j
     break
 print(s)
 print(*m1)


# cook your dish here
for _ in range(int(input())):
 n,m=list(map(int, input().split()))
 c=list(map(int, input().split()))
 l=[0]*n 
 total=0
 
 for i in range(n):
  d,f,b=list(map(int, input().split()))
  if c[d-1]>0:
   c[d-1]-=1 
   total+=f 
   l[i]=d 
   
  else:
   total+=b 

 t=m-1 
 print(total) 
 for i in l:
  if i>0:
   print(i, end=' ')
   
  else:
   while True:
    if c[t]>0:
     print(t+1, end=' ')
     c[t]-=1
     if c[t]==0:
      t-=1 
     break
    
    else:
     t-=1 
   
 print('') 

# cook your dish here
for _ in range(int(input())):
 n,m=list(map(int, input().split()))
 c=list(map(int, input().split()))
 l = []
 l1=[0]*n 
 total=0
 
 for i in range(n):
  d,f,b=list(map(int, input().split()))
  if c[d-1]>0:
   c[d-1]-=1 
   total+=f 
   l1[i]=d 
   
  else:
   total+=b 
   l.append(b)
 
 t=m-1 
 print(total) 
 for i in l1:
  if i>0:
   print(i, end=' ')
   
  else:
   while True:
    if c[t]>0:
     print(t+1, end=' ')
     c[t]-=1
     if c[t]==0:
      t-=1 
     break
    
    else:
     t-=1 
   
 print('') 

t=int(input())
for i in range(t):
 n,m=list(map(int,input().split()))
 l=[0]+list(map(int,input().split()))
 s=0
 c=0
 m1=[]
 for i in range(n):
  d,f,b=list(map(int,input().split()))
  if(l[d]>0):
   m1.append(d)
   s+=f
   l[d]-=1
  else:
   m1.append(0)
   s+=b
 for i in range(n):
  if(m1[i]==0):
   for j in range(c,m+1):
    if(l[j]>0):
     m1[i]=j
     l[j]-=1
     c=j
     break
 print(s)
 print(*m1)
 
    
   
  
 
 


t = int(input())
for _ in range(t):
 n,m = map(int,input().split())
 flav = list(map(int,input().split()))
 ans = []
 res = 0
 k = 0
 for i in range(n):
  d,f,b = map(int,input().split())
  if flav[d-1] == 0:
   res += b
   ans.append(-1)
   k+=1
  else:
   flav[d-1]-=1
   res += f
   ans.append(d)
 l = []
 for i in range(m):
  while flav[i]!=0 and k!=0:
   flav[i]-=1;
   k-=1
   l.append(i+1)
 
 print(res)
 c = 0
 for i in range(n):
  if ans[i] == -1:
   print(l[c],end =' ')
   c+=1
  else:
   print(ans[i],end=' ')
 print()

for _ in range(int(input())):
 
 n, m = list(map(int,input().split()))
 
 l= list(map(int,input().split()))
 
 k=[0]*n
 ans=0
 
 for i in range(n):
  
  d,f,b = list(map(int,input().split()))
  
  if l[d-1]!=0:
   l[d-1]-=1
   k[i]=d
   ans+=f
  else:
   ans+=b
 j=0 
 for i in range(m):
  
  if l[i]!=0:
   
   while(j<n and l[i]>0):
    
    if k[j]==0:
     l[i]-=1
     k[j]=i+1
    j+=1
    
 print(ans)
 print(*k)
   
   
   
   


for _ in range(int(input())):
 
 n, m = list(map(int,input().split()))
 
 l= list(map(int,input().split()))
 
 k=[0]*n
 ans=0
 
 for i in range(n):
  
  d,f,b = list(map(int,input().split()))
  
  if l[d-1]!=0:
   l[d-1]-=1
   k[i]=d
   ans+=f
  else:
   ans+=b
 j=0 
 for i in range(m):
  
  if l[i]!=0:
   
   while(j<n and l[i]>0):
    
    if k[j]==0:
     l[i]-=1
     k[j]=i+1
    j+=1
    
 print(ans)
 print(*k)
     
    
   
   
   
   
   
   
   
   
   
   


for _ in range(int(input())):
 
 n, m = list(map(int,input().split()))
 
 l= list(map(int,input().split()))
 
 k=[0]*n
 ans=0
 
 for i in range(n):
  
  d,f,b = list(map(int,input().split()))
  
  if l[d-1]!=0:
   l[d-1]-=1
   k[i]=d
   ans+=f
  else:
   ans+=b
 j=0 
 for i in range(m):
  
  if l[i]!=0:
   
   while(j<n and l[i]>0):
    
    if k[j]==0:
     l[i]-=1
     k[j]=i+1
    j+=1
    
 print(ans)
 print(*k)
     
    
   
   
   
   
   
   
   
   
   
   
   
   


for _ in range(int(input())):
 
 n, m = list(map(int,input().split()))
 
 l= list(map(int,input().split()))
 
 k=[0]*n
 ans=0
 
 for i in range(n):
  
  d,f,b = list(map(int,input().split()))
  
  if l[d-1]!=0:
   l[d-1]-=1
   k[i]=d
   ans+=f
  else:
   ans+=b
 j=0 
 for i in range(m):
  
  if l[i]!=0:
   
   while(j<n and l[i]>0):
    
    if k[j]==0:
     l[i]-=1
     k[j]=i+1
    j+=1
    
 print(ans)
 print(*k)
     
    
   
   
   
   
   
   
   
   
   
   
   
   
   


for _ in range(int(input())):
 n,m=map(int,input().split())
 drinks=list(map(int,input().split()))
 output=0
 remain=[]
 olist=[0]*n 
 for i in range(n):
  demand,goodp,badp=map(int,input().split())
  if drinks[demand-1]!=0:
   drinks[demand-1]-= 1 
   olist[i]=demand 
   output+=goodp 
  else:
   remain.append(i)
   output+=badp 
 rj=0
 for i in range(len(drinks)):
  if drinks[i]==0:
   continue
  while(drinks[i]>0):
   if rj==len(remain):
    break
   olist[remain[rj]]=i+1
   rj+=1 
   drinks[i]-=1
  if rj==len(remain):
   break
 
 print(output)
 for i in olist:
  print(i,end=" ")
 print()

# cook your dish here
for _ in range(int(input())):
 n,m=list(map(int,input().split()))
 c=list(map(int,input().split()))
 d={}
 for i in range(len(c)):
  d[i+1]=c[i]
 ans=[]
 profit=0
 r_1=0
 for i in range(n):
  t_1,t_2,t_3=list(map(int,input().split()))
  if d[t_1]>0:
   profit+=t_2
   d[t_1]-=1
   ans.append(t_1)
  else:
   profit+=t_3
   r_1+=1
   ans.append('')
 print(profit)
 rem=[]
 for i in d:
  if d[i]>0:
   rem+=[i]*d[i]
   d[i]=0
  if len(rem)>=r_1:
   break
 j=0
 for i in range(len(ans)):
  if ans[i]=='':
   ans[i]=rem[j]
   j+=1
 print(*ans)


for _ in range(int(input())):
 n,m=list(map(int,input().split()))
 c=list(map(int,input().split()))
 d={}
 for i in range(len(c)):
  d[i+1]=c[i]
 ans=[]
 profit=0
 r_1=0
 for i in range(n):
  t_1,t_2,t_3=list(map(int,input().split()))
  if d[t_1]>0:
   profit+=t_2
   d[t_1]-=1
   ans.append(t_1)
  else:
   profit+=t_3
   r_1+=1
   ans.append('')
 print(profit)
 rem=[]
 for i in d:
  if d[i]>0:
   rem+=[i]*d[i]
   d[i]=0
  if len(rem)>=r_1:
   break
 j=0
 for i in range(len(ans)):
  if ans[i]=='':
   ans[i]=rem[j]
   j+=1
 print(*ans)


t=int(input())
while(t>0):
 n,k=list(map(int,input().split()))
 l=[0]+list(map(int,input().split()))
 s=0
 m=[]
 for i in range(n):
  d,f,b=list(map(int,input().split()))
  if(l[d]>0):
   l[d]-=1
   s+=f
   m.append(d)
  else:
   s+=b
   m.append(0)
 c=0
 for i in range(n):
  if(m[i]==0):
   for j in range(c,k+1):
    if(l[j]>0):
     c=j
     m[i]=j
     l[j]-=1
     break
 print(s) 
 print(*m)
 t-=1


for _ in range(int(input())):
 n,m=map(int,input().split())
 c=list(map(int,input().split()))
 l=[]
 ans=0
 for z in range(n):
  d,f,b=map(int,input().split())
  l.append([d,f,b])
 v=[0]*len(l)
 res=[0]*n
 a=[]
 for j,i in enumerate(l):
  if(c[i[0]-1]>0):
   c[i[0]-1]-=1 
   ans+=i[1]
   v[j]=1
   res[j]=i[0]
 s=len(l)
 lc=len(c)
 count=0
 for i in range(s):
  if(v[i]==0):
   ans+=l[i][2]
   count+=1 
 k=[]
 for i in range(lc):
  if(c[i]>0):
   while(c[i]>0 and count>0):
    c[i]-=1 
    count-=1 
    k.append(i+1)
 kl=len(res)
 for i in range(kl):
  if(res[i]==0):
   res[i]=k.pop()
 print(ans) 
 for i in res:
  print(i,end=' ')
 print()

for _ in range(int(input())):
 n,m=map(int,input().split())
 c=list(map(int,input().split()))
 l=[]
 ans=0
 for z in range(n):
  d,f,b=map(int,input().split())
  l.append([d,f,b])
 v=[0]*len(l)
 res=[0]*n
 a=[]
 for j,i in enumerate(l):
  if(c[i[0]-1]>0):
   c[i[0]-1]-=1 
   ans+=i[1]
   v[j]=1
   res[j]=i[0]
 s=len(l)
 lc=len(c)
 count=0
 for i in range(s):
  if(v[i]==0):
   ans+=l[i][2]
   count+=1 
 k=[]
 for i in range(lc):
  if(c[i]>0):
   while(c[i]>0 and count>0):
    c[i]-=1 
    count-=1 
    k.append(i+1)
 kl=len(res)
 for i in range(kl):
  if(res[i]==0):
   res[i]=k.pop()
 print(ans) 
 for i in res:
  print(i,end=' ')
 print()

# cook your dish here
test=int(input())
for _ in range(test):
 n,m=map(int,input().split(" "))
 c=[int(j) for j in input().split(" ")]
 revenue=0
 finallist=[]
 remlist=[]
 p=0
 customer=[]
 for j in range(n):
  customer.append([int(j) for j in input().split(" ")])
  if c[customer[j][0]-1]>0:
   revenue += customer[j][1]
   finallist.append(customer[j][0])
   c[customer[j][0]-1]-=1
  else:
   remlist.append(p)
  p+=1

 k=0
 while len(remlist):
  if c[k]>0:
   revenue+=customer[remlist[0]][2]
   finallist.insert(remlist[0],k+1)
   c[k]-=1
   remlist.remove(remlist[0])
  else:
   k+=1
 print(revenue)
 print(*finallist, sep = " ")

t=int(input())
for i in range(t):
 # n = number of customers, m = number of flavors
 n , m = map(int,input().split(" "))
 # c for number of each flavor
 c = [int(j) for j in input().split(" ")]
 # customer for customer preference data

 revenue = 0
 finallist = []
 remlist = []
 p=0

 customer = []
 for j in range(n):
  customer.append([int(j) for j in input().split(" ")])
  if c[customer[j][0]-1]>0:
   revenue += customer[j][1]
   finallist.append(customer[j][0])
   c[customer[j][0]-1]-=1
  else:
   remlist.append(p)
  p+=1

 k=0
 while len(remlist):
  if c[k]>0:
   revenue += customer[remlist[0]][2]
   finallist.insert(remlist[0],k+1)
   c[k]-=1
   remlist.remove(remlist[0])
  else:
   k+=1
     
 print(revenue)
 print(*finallist, sep = " ")

# cook your dish here
for _ in range(int(input())):
 n,m=map(int,input().split())
 l=[0]*(m+1)
 assign=[0]*(n+1)
 s=0
 k=list(map(int,input().split()))
 for i in range(m):
  l[i+1]=k[i]
 for i in range(n):
  d,f,b=map(int,input().split())
  if(l[d]>0):
   l[d]-=1
   s+=f
   assign[i]=d
  else:
   s+=b
 j=0
 while(l[j]==0):
  j+=1
 for i in range(n):
  if(assign[i]==0):
   if(l[j]!=0):
    l[j]-=1
    assign[i]=j
   else:
    while(l[j]==0):
     j+=1
    l[j]-=1
    assign[i]=j
 print(s)
 for i in range(n):
  print(assign[i],end=" ")
 print()
  

t=int(input())
for i in range(t):
 n,m=[int(x) for x in input().split()]
 arr=[]
 amt=[int(x) for x in input().split()]
 cost=0
 brr=[0 for i in range(n)]
 for j in range(n):
  arr.append([int(y) for y in input().split()])
  if(amt[arr[j][0]-1]>0):
   amt[arr[j][0]-1]-=1
   cost+=arr[j][1]
   brr[j]=arr[j][0]
 r=0
 for j in range(n):
  if(brr[j]==0):
   for k in range(r,m):
    if(amt[k]>0):
     r=k
     amt[k]-=1
     cost+=arr[j][2]
     brr[j]=k+1
     break
 print(cost)
 for j in range(n-1):
  print(brr[j],end=" ")
 print(brr[-1])


t=int(input())
for i in range(t):
 n,m=[int(x) for x in input().split()]
 arr=[]
 amt=[int(x) for x in input().split()]
 cost=0
 brr=[0 for i in range(n)]
 for j in range(n):
  arr.append([int(y) for y in input().split()])
  if(amt[arr[j][0]-1]>0):
   amt[arr[j][0]-1]-=1
   cost+=arr[j][1]
   brr[j]=arr[j][0]
 r=0
 for j in range(n):
  if(brr[j]==0):
   for k in range(r,m):
    if(amt[k]>0):
     r=k
     amt[k]-=1
     cost+=arr[j][2]
     brr[j]=k+1
     break
 print(cost)
 for j in range(n-1):
  print(brr[j],end=" ")
 print(brr[-1])


t=int(input())
for i in range(t):
 n,m=[int(x) for x in input().split()]
 amt=[int(x) for x in input().split()]
 cost=0
 brr=[0 for x in range(n)]
 crr=[]
 for j in range(n):
  d,f,b=[int(x) for x in input().split()]
  if(amt[d-1]>0):
   amt[d-1]-=1
   cost+=f
   brr[j]=d
  else:
   crr.append(j)
   cost+=b
 r=0
 for j in crr:
  for k in range(r,m):
   if(amt[k]>0):
    r=k
    amt[k]-=1
    brr[j]=k+1
    break
 print(cost)
 for j in range(n-1):
  print(brr[j],end=" ")
 print(brr[-1])


t=int(input())
for i in range(t):
 d=[]
 f=[]
 b=[]
 profit=0
 
 n,m=[int(x) for x in input().split()]

 order=[0 for j in range(n)]
 flav=[int(x) for x in input().split()]
 for j in range(n):
  inp=[int(x) for x in input().split()]
  d.append(inp[0])
  f.append(inp[1])
  b.append(inp[2])

 for j in range(n):
  if(flav[d[j]-1])>0:
   profit=profit+f[j]
   flav[d[j]-1]-=1
   order[j]=d[j]
 flag=0
 for j in range(n):
  if(order[j]==0):
   for k in range(flag,n):
    if(flav[flag]>0):
     order[j]=flag+1
     flav[flag]-=1
     profit+=b[j]
     break
    else:
     flag+=1

 print(profit)
 for k in range(len(order)-1):
  print(order[k],end=" ")
 print(order[-1])