Osvetlitev
Vzdolž ravne ulice dolžine $M$ metrov je nameščenih $N$ uličnih luči. Nekatere luči so se v preteklosti pokvarile in so jih morali zamenjati. Zato luči niso enakomerno razporejene in nimajo enake moči osvetlitve. Luči so oštevilčene s celimi števili od $1$ do $N$ in za $i$-to luč poznamo njeno lokacijo $x_i$ (razdalja v nekih dolžinskih enotah od začetka ulice) in razdaljo $d_i$ (v istih enotah), ki jo ta luč osvetljuje na vsako stran. Luč $i$ torej osvetljuje interval $[x_i-d_i, x_i+d_i]$. Lahko se zgodi, da je več luči nameščenih na istem mestu. Napišite program, ki bo iz podatkov o ulici in lučeh na njej izračunal, koliko dolžinskih enot ulice je neosvetljene.
Omejitve podatkov:
- $1 \leq M \leq 10^{9}$ (pri merjenju smo lahko zelo natančni in uporabljamo res majhne dolžinske enote)
- $0 \leq N \leq 10\,000$ (luči je lahko kar precej)
- $0 \leq x_i \leq M$ (luči bodo locirane nekje vzdolž ulice)
- $0 \leq d_i \leq 10^{9}$ (moč luči je lahko tudi zelo velika)
Vhodni in izhodni podatki:
V prvi vrstici je podana dolžina ulice $M$, v drugi vrstici pa število luči $N$. Sledi $N$ vrstic, kjer $i$-ta vrstica opisuje $i$-to luč z njeno lokacijo $x_i$ in močjo $d_i$. Izpišite eno samo vrstico s skupno dolžino neosvetljene ulice.
Primer vhoda:
30
7
10 2
23 2
14 1
4 1
14 4
11 5
1 2
Pravilen izhod:
9
Namigi za prvič:
Bodite natančni pri posebnih primerih, npr. ko sveti luč čez rob ulice, ali pri $d_i=0$ (pokvarjena luč), ali $N=0$ (ulica brez luči). Ocenite in tudi preverite učinkovitost svoje rešitve pri največji velikosti vhodnih podatkov (veliko zelo močnih luči), da ne bo presenečenj pri ocenjevanju.