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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "# cook your dish here\nfor _ in range(int(input())):\n n,m=list(map(int,input().split()))\n c=list(map(int,input().split()))\n d={}\n for i in range(len(c)):\n  d[i+1]=c[i]\n ans=[]\n profit=0\n r_1=0\n for i in range(n):\n  t_1,t_2,t_3=list(map(int,input().split()))\n  if d[t_1]>0:\n   profit+=t_2\n   d[t_1]-=1\n   ans.append(t_1)\n  else:\n   profit+=t_3\n   r_1+=1\n   ans.append('')\n print(profit)\n rem=[]\n for i in d:\n  if d[i]>0:\n   rem+=[i]*d[i]\n   d[i]=0\n  if len(rem)>=r_1:\n   break\n j=0\n for i in range(len(ans)):\n  if ans[i]=='':\n   ans[i]=rem[j]\n   j+=1\n print(*ans)\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13649