Մաքսիմալ բոնուս հզորությունը

Պատկերացրեք դուք գտնվում եք վիրտուալ խաղում և ձեր հերոսին կարող եք հզորացնել նրան ավելացնելով տրված n իրերը ինչ-որ հերթականությամբ (հերթականությունը ընտրում եք դուք)։ Ձեր հզորությունը չի կարող գերազանցել տրված k թիվը։ n իրերից i-րդի հզորությունը հավասար է p[i]-ի և նաև տրված են p[i] հատ տարբեր բոնուս հզորություններ, նշանակենք դրանք w[i][1], w[i][2], ..., w[i][p[i]]-ով։ Իրերը ձեր հերոսին ավելացնելուց, աշխատում է հետևյալ ալգորիթմը։ Ենթադրենք, դուք ընտրել եք, թե ինչ հերթականությամբ եք ուզում ավելացնել իրերը ձեր հերոսի վրա. ։ Ենթադրենք, այս պահին դուք ցանկանում եք ավելացնել j-րդ իրը և ձեր հերոսի հզորությունը մինչև այդ իրը ավելացնելը հավասար է sum-ի.