Տիեզերական Ադմիրալ Մարտինը և Այլմոլորակայինները

Ուշադրություն․ այս խնդրի ժամանակային սահմանափակումը վայրկյան է և թեստերը շատ են։ Լուծման ստուգումը կարող է մինչև րոպե տևել։ Խնդրում ենք այդ ընթացքում ուրիշ խնդրի վրա աշխատել, կամ սպասել համբերությամբ։

Տիեզերական Ադմիրալ Մարտինը պլանավորում է իր լազերային զենքերով ջախջախել թշնամի այլմոլորակայիններին (խաղաղ նպատակներով)։ Մոլորակները, ինչպես հայտնի է, հարթ են։ Թշնամի մոլորակի օդային տարածքը կարելի է պատկերացնել որպես տողից և սյունից կազմված ցանց։ Տողերը համարակալված են -ից մինչև ՝ վերևից ներքև, իսկ սյուները՝ -ից մինչև ՝ ձախից աջ։

Յուրաքանչյուր տողում կա ճիշտ մեկ սահող պատնեշ, նախատեսված լազերային հարձակումներից պաշտպանության համար։ Սկզբում -րդ տողի պատնեշը զբաղեցնում է -ից մինչև սյուները: Ադմիրալ Մարտինը կարող է վճարել դրամ և -րդ պատնեշի կառավարման համակարգի վրա կիբերհարձակում գործել, որից հետո կարելի է -րդ պատնեշը հորիզոնական տեղաշարժել (իհարկե, առանց ցանցի սահմաններից դուրս բերելու)։

Յուրաքանչյուր սյան վերևում տեղադրված է ներքև ուղղված լազեր։ Եթե որևէ սահող պատնեշ գտնվում է -րդ սյան մեջ, ապա այն կփակի -րդ սյան լազերի ճանապարհը։

Մարտինը ունի դրամ ընդհանուր բյուջե։ Նա ցանկանում է առավելագույն դարձնել այն լազերների քանակը, որոնց պատնեշները չեն խանգարի, օպտիմալ ձևով կիբերհարձակումներ անելով և պատնեշներ սահեցնելով։ Գտեք առավելագույնը քանի չփակված լազեր կարող է ստացվել։

Մուտքային տվյալները

Ձեր ծրագիրը պետք է կարդա ստանդարտ մուտքից։

Առաջին տողում տրված են երեք ամբողջ թվեր՝ , , , որոնք նկարագրում են համապատասխանաբար տողերի քանակը, սյուների քանակը և բյուջեն։

Հաջորդ տողերից յուրաքանչյուրում տրված են երեք ամբողջ թվեր՝ , , , որոնք նկարագրում են -րդ տողի սահող պատնեշը։

Ելքային տվյալները

Տպեք մեկ ամբողջ թիվ՝ հնարավոր առավելագույն չփակված լազերների քանակը։

Օրինակներ

3 10 10
2 5 9
1 3 1
4 7 10

6

10 10 50
8 8 0
3 3 0
6 6 2
7 7 9
1 1 50
5 5 21
6 6 4
10 10 4
10 10 3
10 10 3

9

4 17 0
2 4 1000000000
6 9 1000000000
8 13 1000000000
15 16 1000000000

4

Ենթախնդիրները

Եթե ենթախնդրում տարրի համար սահմանափակում նշված չէ, ապա տեղի ունեն հետևյալ սահմանափակումները․

• ,

• ,

• (),

• ():