Description

This maze has a total of $n$ caves. There are many one-way tunnels between the caves, so many that it is hard to count them.

However, after analysis, it is found that:

These tunnels can be divided into $m$ groups. For each group, for every cave with an index in the interval $[s_l,s_r]$, and every cave with an index in the interval $[t_l,t_r]$, there is a tunnel between them. Each group contains a total of $(s_r-s_l+1)\cdot (t_r-t_l+1)$ tunnels, and the time to pass through any tunnel in the same group is the same.

To further save time, Steve can dig new tunnels.

However, each cave has different properties, which makes digging tunnels of different difficulty. Some caves cannot even dig tunnels.

Specifically, the $i$-th cave has a value $v_i$. $v_i=0$ means tunnels cannot be dug from it. For other values, it means that starting from cave $i$, digging a tunnel to cave $j$ and arriving at cave $j$ costs $|i-j|*v_i$ time.

Steve wants to reach cave $n$ in the shortest time, and decides not to limit the number of tunnels he digs.

Now, you need to tell Steve the minimum time required.

If possible, you should help Steve find an optimal plan.

Input Format

The first line contains two integers $n,m$.

The next line contains $n$ integers $v_1,v_2,...,v_n$.

The next $m$ lines each describe a group of tunnels.

Each line contains $5$ integers $s_l,s_r,t_l,t_r,w$, where $w$ is the travel time.

Output Format

If there is no solution, output only one line with one integer $-1$.

If there is a solution, output in the following format:

The first line contains an integer $t$, which is the minimum time spent.

If you cannot provide a plan, output an integer $0$ on the second line.

If you can provide a plan, output an integer $c$ on the second line, and output $c$ integers on the third line, representing (in order) the cave indices visited by one optimal plan.

You do not need to tell Steve whether each tunnel used is dug, or which group it belongs to.

6 2
0 1 2 0 0 0
1 1 2 3 5
4 5 6 6 2

9
3
1 2 6

6 2
0 1 2 0 0 0
1 1 2 3 5
4 5 6 6 2

9
4
1 3 4 6

Hint

Sample 1: From cave $1$ to cave $2$ use the first group tunnel, then from cave $2$ to cave $6$ dig a tunnel, costing $1*(6-2)=4$ time.

Sample 2: From cave $1$ to cave $3$ use the first group tunnel, then from cave $3$ to cave $4$ dig a tunnel, costing $2*(4-3)=2$, then from cave $4$ to cave $6$ use the second group tunnel.

Each subtask includes two test points, and the lower score is taken.

For each test point:

If the output format is wrong, then this test point scores $0$.

If you do not output the correct time, then this test point scores $0$.

If you output the correct time but do not give a plan, then you can get half of the score of this test point (the score of each test point is rounded down).

If you give a wrong plan, then you may get half of the score of this test point, or get $0$.

If you give a correct plan, then you can get the full score of this test point.

The two outputs above can both get full score. Another plan is $1 2 4 6$.

If you output:

9
0

then you can get half of the score for this test point.

Constraints:

$1\le w,v_i \le 10^9$.

Special Property 1: All $v_i=0$.

Special Property 2: All $v_i \in \{0,k\}$, where $k$ is a constant.

Special Property 3: All $s_l=s_r,t_l=t_r$.

It is guaranteed that there exists a plan to reach cave $n$.

About outputting a wrong plan:

If the output satisfies $2\leq c\leq n$, the visited nodes start with $1$ and end with $n$, and all intermediate nodes are integers in $(1,n)$, then this set of output may be an optimal solution, and you can get half of the score.

Otherwise, you get $0$.

Do not worry about the SPJ TLE/MLE.

Translated by ChatGPT 5