АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Лена нь олимпиадын өмнөх урдчилсан тэмцээнүүдэд орох гэж байна. Тэрээр өөрийн шүтлэгтэй бөгөөд Аз- аа хамгийн их хуримтлуулахыг хүсч байгаа.

Лена тэмцээнд хожигдоход түүний аз тухайн тэмцээний L[i] оноогоор нэмэгдэж, хожиход L[i.] оноогоор багасдаг.

Гэхдээ тэр бүх чухал тэмцээнд хожигдоод байж болохгүй. Тухайн оролцож байгаа тэмцээнийгээ чухал (1), чухал биш (0) гэж үнэлдэг.

Лена чухал гэж үзсэн тэмцээнүүддээ k-аас дээш ялагдаж болохгүй.  Лена маш авъяаслаг учир хүсвэл ямар ч тэмцээнд ялж чадна.

Тайлбар:

 k=2 үед

Contest                    L[i]          T[i]

1                             5              1

2                             1              1

3                             4              0

Түүнд 1 болон 2  дах тэмцээнүүд чухал. Харин 3 бол чухал биш. Тэр чухал тэмцээндээ k=2 -оос дээш ялагдаж болохгүй.

3 тэмцээн байгаа тул зааваал 1 тэмцээнд түрүүлэх ёстой. Иймд лена 5+4-1=8 хамгийн ихдээ 8 нь аз цуглуулж чадна.

Оролт :

1 ≤ n ≤ 100

0 ≤ k ≤ n

1 ≤ L[i] ≤ 10⁴

T[i] зөвхөн {0,1}  

Гаралт:

Түүний цуглуулж чадах хамгийн их аз

Жишээ:

Оролт:

6 3

5 1

2 1

1 1

8 1

10 0

5 0  

Гаралт:

29

Орчуулсан  : Дархан-Уул аймгийн Союз сургуулийн 12-р ангийн сурагч Б.Сумьяабазар