Multa per eccesso di velocità#11155
Sempre pronta a causare guai, la mucca Bessie ha rubato il trattore del fattore John e ci si è avventurata lungo una strada!
La strada ha una lunghezza esatta di miglia. Bessie percorre l'intera strada dall'inizio alla fine, dopodiché viene fermata da un poliziotto. Questi le fa una multa per eccesso di velocità, per patente scaduta e per guida in stato di mucca. Bessie ammette che le ultime due multe siano probabilmente meritate, ma dubita che il poliziotto abbia calcolato correttamente la multa per eccesso di velocità. Vuole quindi verificare da sola se abbia effettivamente superato il limite di velocità in qualche tratto del percorso.
La strada è divisa in segmenti. Per ciascun segmento sono indicati la sua lunghezza — un numero intero positivo di miglia — e il limite di velocità — un numero intero compreso tra e miglia orarie. Poiché la lunghezza totale della strada è di miglia, le lunghezze di tutti gli segmenti sommate danno .
Ad esempio, la strada potrebbe iniziare con un segmento di miglia con limite di velocità di miglia orarie, seguito da un segmento di miglia con limite di velocità di miglia orarie.
Anche il percorso di Bessie è composto da segmenti. In ciascun segmento, Bessie percorre un determinato numero intero positivo di miglia a una certa velocità intera. Ad esempio, potrebbe prima percorrere miglia a miglia orarie, e poi altre miglia a miglia orarie. La lunghezza totale di tutti gli segmenti è anch'essa pari a miglia. La velocità massima del trattore del fattore John è di miglia orarie.
Sulla base delle informazioni sopra riportate, determina il massimo superamento del limite di velocità stabilito che Bessie ha commesso in un qualsiasi tratto del suo percorso.
La prima riga contiene due numeri interi e . Nelle successive righe vengono descritti i segmenti della strada: ogni riga contiene due numeri interi — la lunghezza del segmento e il limite di velocità stabilito su di esso.
Nelle successive righe vengono descritti i segmenti del percorso di Bessie: ogni riga contiene due numeri interi — la lunghezza del segmento e la velocità con cui Bessie lo ha percorso.
Stampa un singolo numero intero — il massimo superamento del limite di velocità stabilito commesso da Bessie in un qualsiasi tratto del percorso. Se Bessie non ha mai superato il limite di velocità, stampa .
In questo esempio, la strada è composta da tre segmenti: miglia con limite di velocità di miglia orarie, poi miglia con limite di miglia orarie e infine miglia con limite di miglia orarie.
Bessie percorre la strada anch'essa in tre segmenti: miglia a miglia orarie, miglia a miglia orarie e miglia a miglia orarie.
Nel primo segmento supera di poco il limite di velocità, ma nell'ultimo segmento la violazione risulta essere la più grave: in una parte di esso supera il limite stabilito di miglia orarie. Pertanto la risposta corretta è .
Esempio 1