Trampolini#9604
Bessie si trova su una griglia bidimensionale, dove può muoversi solo in direzioni parallele agli assi coordinati. Inizia il suo movimento dal punto e vuole arrivare al punto . Per aiutarla, sulla griglia sono posizionati trampolini. Ogni trampolino inizia in un punto fisso (x_1, y_1) e, se Bessie lo utilizza, la sposta nel punto (x_2, y_2).
Bessie è una mucca orientata al progresso, quindi si concede di muoversi solo verso l'alto o verso destra, senza mai muoversi a sinistra o verso il basso. Analogamente, ogni trampolino è configurato in modo da non spostarla mai a sinistra o verso il basso. In altre parole, per ogni trampolino valgono le condizioni x_1 \le x_2 e y_1 \le y_2.
Qual è la distanza minima che Bessie deve percorrere a piedi per raggiungere il punto ?
Nella prima riga sono contenuti due numeri interi n~(1 \le n \le 10^9) e p~(1 \le p \le 10^5).
In ciascuna delle successive righe sono contenuti quattro numeri interi x_1, y_1, x_2, y_2, che descrivono un trampolino che sposta Bessie dal punto (x_1, y_1) al punto (x_2, y_2), dove valgono le condizioni x_1 \le x_2 e y_1 \le y_2.
Tutti i punti di partenza e di arrivo dei trampolini, così come il punto di destinazione, sono distinti.
Stampate un singolo numero intero — la distanza minima che Bessie deve percorrere a piedi per raggiungere il punto .
Il percorso ottimale di Bessie è il seguente:
Bessie va dal punto al punto , percorrendo una distanza di .
Bessie utilizza un trampolino per spostarsi dal punto al punto .
Bessie va dal punto al punto , percorrendo una distanza di .
Bessie utilizza un trampolino per spostarsi dal punto al punto .
Bessie va dal punto al punto , percorrendo una distanza di .
La lunghezza totale del percorso effettuato a piedi è di unità.
Esempio 1