Note: This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please, take a look at the sample explanation to ensure that you understand the problem correctly.

Given a CPU which can work for $W$ minutes and can handle one process at a time.

$N$ process are given with their benefit value $B[i]$, run time $R[i]$ (in minutes) and deadline $D[i]$ (in minutes). All process are available from time $T = 0$.

Find a subset of $N$ processes and their order for execution, with maximum possible sum of benefit value. They should be handled by CPU without collision and satisfying their deadlines.

The goal is to maximize $Z = \sum B[j]$.

Note:

• $R[i]$ for a process can also be greater than $W$.
• CPU will start the process immediately once that will available.
• You can use some process atmost once.
• Process can't be under execution beyond deadline.

Input

• First line contains $W$, denoting time for which CPU works.
• Next line contain $N$, denoting number of processes available.
• Next $N$ lines contain $3$ integers $B[i] \ R[i] \ D[i]$, parameters corresponding to the $i^{th}$ process.

Output

• Print $X$ the size of the subset selected.
• In the next line, print $X$ space separated integers, denoting the processes in the order that are handled by CPU.

Constraints

$1 \le N \le 10^5 \\ 1 \le W, D[i] \le 10^9 \\ 1 \le R[i], B[i] \le 10^6$

50% of the test files have $N = 10^5$.

50% of the test files have $N \le 10^3$

Verdict and scoring 

Your score is equal to the sum of the values of all test files. The value of each test file is equal to the value of $Z$ that you found.

If the output format if wrong or $X$ selected process does not meet their deadlines or total runtime exceeds $W$ or collide Wrong Answer verdict will be recieved.