Maze Caves and Tunnel Digging

There are \(n\) caves and many one-way tunnels. The tunnels are divided into \(m\) groups. For each group, for every cave \(i\) in the interval \([s_l, s_r]\) and every cave \(j\) in the interval \([t_l, t_r]\), there is a tunnel from \(i\) to \(j\) with travel time \(d\). That is, each group contains \((s_r-s_l+1)\times(t_r-t_l+1)\) tunnels, and every tunnel in the same group takes the same time.

In addition, Steve can dig new tunnels. Each cave \(i\) is associated with a value \(v_i\). If \(v_i = 0\) then digging a tunnel from cave \(i\) is not allowed; otherwise, digging a tunnel from cave \(i\) to cave \(j\) will cost \(|i-j|\times v_i\) time.

Steve starts at cave 1 and wants to reach cave \(n\) in the shortest possible time. If an optimal solution exists, output both the minimum time and one optimal plan (i.e. the sequence of caves to travel through).

inputFormat

The first line contains two integers \(n\) and \(m\).
The second line contains \(n\) integers \(v_1, v_2, \dots, v_n\) where \(v_i\) is the digging cost for cave \(i\) (if \(v_i = 0\), no tunnel can be dug from cave \(i\)).
Each of the next \(m\) lines contains five integers: \(s_l\), \(s_r\), \(t_l\), \(t_r\), and \(d\), representing a tunnel group. For every \(i\) with \(s_l \le i \le s_r\) and every \(j\) with \(t_l \le j \le t_r\), there is a directed tunnel from cave \(i\) to cave \(j\) with travel time \(d\).

outputFormat

If cave \(n\) is unreachable, output -1.
Otherwise, on the first line output the minimum time required to reach cave \(n\).
On the second line, output the number of caves on an optimal path followed by the sequence of cave indices (starting with 1 and ending with \(n\)) separated by spaces.

sample

4 1
1 2 0 3
1 1 2 2 2

3
2 1 4