Vrsar

Το Vrsar είναι ένα μικρό παραθαλάσσιο χωριό που αποτελείται από ~n~ λόφους. Όλως περιέργως, όλοι οι λόφοι, όταν τους κοιτάζουμε από τη θάλασσα, είναι τοποθετημένοι ο ένας πίσω από τον άλλο έτσι που ο ~i~-οστός λόφος είναι ~x_{i}~ μέτρα μακριά από τη θάλασσα. Στην κορυφή κάθε λόφου, υπάρχει ένα παγοδρόμιο. Όλα τα παγοδρόμια ανοίγουν ταυτόχρονα κάθε μέρα, αλλά δεν κλείνουν την ίδια στιγμή: το ~i~-οστό παγοδρόμιο είναι ανοιχτό για ~t_{i}~ λεπτά.

Η Iva και η Mia έχουν έρθει στο Vrsar και θα παραμείνουν εδώ για ~m~ ημέρες. Η Iva και η Mia αγαπούν το πατινάζ και θέλουν να κάνουν κάθε μέρα που περνούν σε αυτήν την πόλη. Στην αρχή της ~i~-οστής ημέρας, βρίσκονται ~a_{i}~ μέτρα μακριά από τη θάλασσα, και η περιπέτειά τους με το πατινάζ ξεκινάει την ίδια στιγμή που ανοίγουν τα παγοδρόμια. Για να φτάσουν σε ένα παγοδρόμιο, πρέπει να περπατήσουν προς αυτό, κινούμενες με ταχύτητα ενός μέτρου το λεπτό. Μπορούν να περπατήσουν τόσο προς τα αριστερά όσο και προς τα δεξιά. Εάν βρίσκονται σε μια θέση όπου υπάρχει λόφος, μπορούν να ανέβουν στον λόφο και να φτάσουν στο παγοδρόμιο στην κορυφή του, ή μπορούν να το παρακάμψουν χωρίς να ανέβουν.

Είναι και οι δυό τους σε πολύ καλή φόρμα, οπότε μπορούν να ανεβαίνουν τον λόφο χωρίς να χρειάζονται περισσότερο χρόνο. Μόλις φτάσουν στην κορυφή, μπορούν να κάνουν πατινάζ για όσο θέλουν ή μέχρι να κλείσει το παγοδρόμιο. Η κατάβαση δεν είναι τόσο εύκολη όσο η ανάβαση. Πρόσφατα έβρεξε και ο δρόμος έχει γίνει ολισθηρός, οπότε χρειάζονται ~s_{i}~ λεπτά για να κατέβουν από τον ~i~-οστό λόφο. Μετά την κατάβαση από έναν λόφο, μπορούν να συνεχίσουν να περπατούν προς το επόμενο παγοδρόμιο.

Η εικόνα δείχνει το πρώτο παράδειγμα. Η Iva και η Mia βρίσκονται στο σημείο εκκίνησης στη θέση ~1~. Περπατούν για ~2~ λεπτά προς το παγοδρόμιο στον λόφο στη θέση ~3~ και κάνουν πατινάζ εκεί για ~5~ λεπτά. Στη συνέχεια, κατεβαίνουν από τον λόφο (σε ~0~ λεπτά), συνεχίζουν να περπατούν για ~3~ λεπτά προς το παγοδρόμιο στον λόφο στη θέση ~6~ και κάνουν πατινάζ εκεί για ~1~ λεπτό. Συνολικά, έχουν κάνει πατινάζ για ~5 + 1 = 6~ λεπτά.

Η Iva και η Mia θέλουν να προσδιορίσουν τον μέγιστο αριθμό λεπτών που μπορούν να κάνουν πατινάζ κάθε μέρα. Σε μία ημέρα, μπορούν να επισκεφτούν οποιονδήποτε αριθμό παγοδρομίων. Καθώς θέλουν να περνάνε περισσότερο χρόνο κάνοντας πατινάζ και λιγότερο χρόνο κάνοντας υπολογισμούς, έχουν απευθυνθεί σε εσάς για βοήθεια. Βοηθήστε τις να επιλύσουν αυτό τους το πρόβλημα!

Σημείωση: Εάν η Iva και η Mia στην αρχή της ημέρας βρίσκονται στην ίδια θέση με έναν λόφο, θα βρίσκονται στο κάτω μέρος του λόφου, και έτσι θα πρέπει να τον ανεβούν αν θέλουν να κάνουν πατινάζ στο παγοδρόμιο στην κορυφή του.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τους ακέραιους ~n~ και ~m\;(1 \le n,m \le 10^{5})~, τον αριθμό των λόφων και τον αριθμό των ημερών.

Η ~i~-οστή από τις επόμενες ~n~ γραμμές θα περιέχει τους ακέραιους ~x_{i}~, ~t_{i}~ και ~s_{i}~ ~(0 \le x_{i}, t_{i}, s_{i} \le 10^{9})~, την απόσταση του ~i~-οστού λόφου από την ακτή, το χρόνο κλεισίματος του παγοδρομίου και τον χρόνο που απαιτείται για την κατάβαση από τον λόφο.

Η τρίτη γραμμή θα περιέχει ~m~ ακεραίους ~a_{i}\;(0 \le a_{i} \le 10^{9})~, την αρχική απόσταση της Iva και της Mia από την ακτή στην αρχή της ~i~-οστής ημέρας.

Έξοδος

Σε μία γραμμή, εκτυπώστε ~m~ ακεραίους, ο ~i~-οστός εκ των οποίων θα είναι ο μέγιστος χρόνος που η Iva και η Mia μπορούν να κάνουν πατινάζ την ~i~-οστή ημέρα.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~8~	~n,m \le 10~
~2~	~17~	~m = 1,\; a_{i} = 0~
~3~	~19~	~n,m \le 1000~
~4~	~26~	Κανένας επιπλέον περιορισμός

Παραδείγματα

input

3 1
3 7 0
6 11 3
10 13 5
1

output

6

Επεξήγηση του πρώτου παραδείγματος:

Ρίξτε μια ματιά στην εικόνα που περιλαμβάνεται στην περιγραφή.

input

3 2
5 10 3
3 6 1
1 5 0
0 3

output

5 8

input

1 3
3 3 3
0 1 2

output

0 1 2