Minimizing Array Range in an Interactive Query Problem

We are given an unknown array \(a[1\dots m]\) (with indices from 1 to \(m\)). In an interactive setting, a participant can query the array with a 5‐tuple \((l, r, p, q, \text{ans})\). For each query the interactive program guarantees that

[ \min_{l\le x\le r}a[x] - \max_{p\le y\le q}a[y] \ge \text{ans} ]

Note that the value \(\text{ans}\) returned does not reveal the exact difference between the two segments, so one cannot recover the actual array elements directly.

Your task is: Given several queries and the corresponding responses, determine the minimum possible value of

[ \max_{1\le x\le m}a[x] - \min_{1\le y\le m}a[y] ]

over all arrays \(a[1\dots m]\) that satisfy the constraints implied by the queries.

Note: For each query a valid array must satisfy that for all indices \(i\in [l,r]\) and \(j\in [p,q]\), it holds that

[ a[i] - a[j] \ge \text{ans}, ]

and you are to choose an array whose overall range is as small as possible.

inputFormat

The first line contains two integers (m) and (q) representing the size of the array and the number of queries, respectively. Each of the following (q) lines contains five integers (l), (r), (p), (q) and (ans) (with (1 \le l \le r \le m) and (1 \le p \le q \le m)), describing one query.

outputFormat

Output one integer, the minimum possible value of (\max_{1\le x\le m}a[x] - \min_{1\le y\le m}a[y]) among all arrays that satisfy the given constraints.

sample

3 2
1 1 2 2 5
3 3 1 1 -2

5