Došla je sezona vašara. Trgovac Vasa bi da ove sezone zaradi dosta para pa hoće da sve isplanira unapred.

U više gradova se organizuju vašari. Vasa zna kog dana u nekom gradu počinje vašar i koliko dana traje. Isto tako zna kolika će gužva biti na tom vašaru i koliko može da zaradi u jednom danu.

Ali Vasa ne planira da prodaje samo u jednom gradu. On planira da se seli iz jednog grada u drugi i želi da mu mi odredimo koliko najviše može da zaradi.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu se nalaze dva broja n i p (1≤ p ≤ n ≤ 1000). Broj n predstavljabroj gradova u kojima se održavaju vašari, a p je rednibroj grada u kojem se Vasa nalazi prvog dana. U svakom odsledećih n redova (svaki red je vezan za jedan grad) senalaze po n + 3 broja: a, b, c, v[1], v[2], ..., v[n](1 ≤ a, b ≤ 200, 1 ≤ c ≤ 1000,0 ≤ v[i] ≤ 400). Broj a predstavlja kog dana utom gradu počinje vašar, b predstavlja koliko dana traje,c predstavlja koliko Vasa može da zaradi u jednom danu na tomvašaru. Broj v[i] predstavlja koliko je potrebno dana da Vasapređe iz tog grada u grad i. Primetite da godina može imati iviše od 365 dana (ali ne više od 400 dana).

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) Treba da se sastoji od samo jednog broja kojipredstavlja koliko Vasa može da zaradi.

Primer 1.

3 2
5 6 5 0 3 3
1 5 2 2 0 1
7 8 3 1 2 0

37

Objašnjenje.

Prva dva dana Vasa prodaje u drugom gradu i zaradi 4. Ondadva dana ne prodaje nego se seli u prvi grad. Tamo prodaje tokomcelog vašara i zaradi 30. Onda tri dana prelazi u trećigrad i u njemu prodaje samo jedan dan, i zaradi 3. Ukupno jezaradio 4 + 30 + 3 = 37.