Achievement Unlocked
Турнир за Купата на Декана, 2012
Time Limit: 0.4s, Memory Limit: 64MiB
Ели играе на популярна компютърна игра. Играта има N подредени по сложност нива, удобно номерирани от 1 до N. Всяко от нивата има определен брой постижения (achievements), които могат да бъдат отключени и биха донесли на момичето точки в играта. Различни постижения могат да носят различен брой точки. Ако дадено ниво има повече от едно възможно постижение, Ели не може да вземе второто и следващите нататък, преди да е взела първото (тоест тя първо отключва първото, после второто и т.н.).

За да стимулират изиграването на различни нива, авторите на играта са разрешили дадено ниво да може да бъде изиграно само ако то има поне един все още неотключен achievement. Изигравайки дадено ниво, Ели отключва първия неотключен achievement и получава точките за него. От друга страна, за да насърчават играта на по-сложни нива, авторите ѝ са направили следната врътка. Изигравайки ниво K, отключва не само следващия неотключен achievement от ниво K, а също така и по един (ако има такъв) във всяко от нивата 1, 2, ..., K-1. Така ако има три нива, първото има три постижения, второто едно, а третото - две, то ако Ели изиграе третото ниво два пъти, тя ще отключи 2 + 1 + 2 = 5 achievement-а. Вижте примера за повече детайли.

Колкото и да е добра Ели, все пак нивата ѝ отнемат известно време. Тя знае колко минути ще ѝ отнеме изиграването на всяко от тях, а също така и какви постижения (колко на брой, за какви точки и в какъв ред) имат те. Елеонора е решила да инвестира най-много M минути за игра. Намерете максималния брой точки, които може да спечели тя в рамките на това време, ако играе нивата в оптимален ред.
Вход
Първият ред на стандартния вход ще съдържа целите числа N и M - съответно колко нива има играта и с колко време разполага Ели. На следващите N реда ще бъдат описани нивата в нарастващ ред на сложност. Всеки от тях ще съдържа между 3 и 52 числа Ri Qi Ai1 Ai2 ... AiQi. Ri задава колко време отнема на Ели за да изиграе ниво i. Qi задава колко achievement-а има ниво i. Следващите Qi на брой числа, задават точките за първото, второто, третото и т.н. постижение за съответното ниво.
Изход
На единствен ред на стандартния изход изведете едно цяло число - колко най-много точки може да спечели Ели, инвестирайки не повече от M минути в игра.
Ограничения
  • 1 ≤ N ≤ 50
  • 1 ≤ M ≤ 125,000
  • 1 ≤ Ri, Qi ≤ 50
  • 1 ≤ Aij ≤ 1,000
Примерен Вход Примерен Изход
5 20 1 1 7 3 6 1 2 3 4 5 6 8 1 4 7 4 10 5 8 7 8 3 5 5 6 42
Една от оптималните стратегии за Ели е да изиграе ниво 1, после ниво 5, после отново ниво 5 и накрая ниво 2, за което тя ще се нуждае от 1 + 8 + 8 + 3 = 20 минути. След изиграването на ниво 1, тя отключва ачийвмънт на стойност 7. След първото изиграване на ниво 5, тя отключва ачийвмънти на стойност 5 от ниво 5, 10 от ниво 4, 4 от ниво 3, 1 от ниво 2 и не отключва ачийвмънт от ниво 1 (тъй като всички вече са отключени). След второто изиграване на ниво 5, тя отключва нов ачийвмънт отново със стойност 5 от него, такъв със стойност 5 от ниво 4, не отключва нищо в ниво 3, ачийвмънт на стойност 2 от ниво 2 и нищо от ниво 1. При изиграването на ниво 2, тя отключва единствено следващия ачийвмънт на това ниво, който е на стойност 3. Общата сума е (7) + (5 + 10 + 4 + 1 + 0) + (5 + 5 + 0 + 2 + 0) + (3 + 0) = 42.

Важно: Забележете, че след като е изиграла веднъж ниво 5, Ели не може да изиграе ниво 3, тъй като в него няма да има неотключени постижения.
Мрън!