Պատկերացրեք դուք գտնվում եք վիրտուալ խաղում և ձեր հերոսին կարող եք հզորացնել նրան ավելացնելով տրված n իրերը ինչ-որ հերթականությամբ (հերթականությունը ընտրում եք դուք)։ Ձեր հզորությունը չի կարող գերազանցել տրված k թիվը։ n իրերից i-րդի հզորությունը հավասար է p[i]-ի և նաև տրված են p[i] հատ տարբեր բոնուս հզորություններ, նշանակենք դրանք w[i][1], w[i][2], ..., w[i][p[i]]-ով։ Իրերը ձեր հերոսին ավելացնելուց, աշխատում է հետևյալ ալգորիթմը։ Ենթադրենք, դուք ընտրել եք, թե ինչ հերթականությամբ եք ուզում ավելացնել իրերը ձեր հերոսի վրա. ։ Ենթադրենք, այս պահին դուք ցանկանում եք ավելացնել j-րդ իրը և ձեր հերոսի հզորությունը մինչև այդ իրը ավելացնելը հավասար է sum-ի.
Եթե , ձեր հզորությանը ավելանում է ով, իսկ բոնուս հզորությանը՝ ով։
Եթե sum ≥ k, ոչինչ տեղի չի ունենում։
Մնացած դեպքերում, ձեր հզորությունը դառնում է k, իսկ բոնուս հզորությունը ավելանում է ով։
Գտնել հնարավոր մաքսիմալ բոնուս հզորությունը, որը դուք կարող եք ձեռք բերել, եթե դուք ընտրում եք իրերի հերթականությունը օպտիմալ ձևով։
Մուտքային տվյալներ
Մուտքային տվյալների առաջին տողում տրված է երկու ամբողջ թիվ՝ n և k, իրերի քանակը և հզորության մաքսիմալ արժեքը համապատասխանաբար։ Հաջորդ n տողերից յուրաքանչյուրը սկսվում է մեկ ամբողջ p[i] թվով, i-րդ իրի հզորությունը, և նաև տրված են p[i] հատ ամբողջ թվեր՝ w[i][1], w[i][2], ..., w[i][p[i]]։
Ելքային տվյալներ
Պետք է արտածել մեկ ամբողջ թիվ՝ հնարավոր մաքսիմալ բոնուս հզորությունը, որը դուք կարող եք ձեռք բերել։
Օրինակ
Մուտք
Ելք
4 5
2 1 3
2 1 1
2 3 1
2 1 3
9
Բացատրություն
Օրինակում հնարավոր մաքսիմալ բոնուս հզորություն հավաքելու համար, իրերը դասավորելու օպտիմալ տարբերակներից մեկը հետևյալն է՝ 4, 1, 3, 2։