Кредибилитет
По многу слаби резултати на натпреварите по информатика, еден ученик конечно сфатил дека треба повеќе да решава задачи. Со ова, тој ќе стане подобар натпреварувач и ќе го зголеми неговиот кредибилитет кај комисијата за натпревари, која одлучува кои ученици ќе ја претставуваат Македонија на меѓународните натпревари. Комисијата има увид во тоа колку решава секој ученик.
Ученикот веќе има одлучено кои задачи ќе ги решава (бројот на задачи N е парен цел број), но сега треба да одлучи и по кој редослед ќе ги решава. На почеток, овој ученик има квалитет на решавање 0 и кредибилитет 0 кај комисијата за натпревари. За секоја задача, познати се две вредности: Xi (колку може да се научи од задачата) и Yi (тежината на задачата). Пo решавање на i-тата задача, квалитетот на решавање на ученикот Q се зголемува за Xi (Q = Q + Xi), а потоа и неговиот кредибилитет кај комисијата веднаш се зголемува за вредноста (Y[i] * Q), каде Q е квалитетот на решавање на ученикот по решавањето на задачата. Се разбира, зависно од редоследот по кој ќе се решаваат задачи, ученикот може да заврши со различен кредибилитет кај комисијата.
Покрај решавање на задачи, ученикот сака, по решавање на точно половина од задачите (N/2) кои ги одбрал, т.е. на полугодие, да помине одредено време на ФИНКИ, за да научи нешто повеќе. За овој период, неговиот квалитет на решавање ќе се подобри за вредност F (цел број), но неговиот кредибилитет кај комисијата ќе остане идентичен.
Напишете програма која ќе ја отпечати максималната вредност за кредибилитетот кај комисијата за натпревари која може да ја има ученикот, доколку тој го направи правилниот распоред за решавање на N-те задачи кои ги одбрал.
Влез
Во првата линија се запишани два цели броја N (2 <= N <= 50) и F (0 <= F <= 100 000), кои го означуваат бројот на задачи, и вредноста F за која ќе се зголеми квалитетот на решавање на ученикот за време на посетата на предавања на ФИНКИ.
Во секој од следните N редови се запишани по два цели броја Xi (1 <= Xi <= 100 000) и Yi (1 <= Yi <= 10), кои ја опишуваат секоја од N-те задачи, како што е објаснето во текстот на задачата.
Забелешка: Во тест случаи кои носат најмалку 30% од поените, N ќе биде цел број помал или еднаков на 6.
Излез
Отпечатете ја бараната максимална вредност за кредибилитетот кој може да го има ученикот кај комисијата за натпревари.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 2 37 10 4 96 5 | излез 1052 |
Објаснување: Најпрвин, ученикот може да ја реши задачата со Xi=96, Yi=5. Неговиот квалитет на решавање ќе се зголеми на Q=96, а кредибилитетот кај комисијата за натпревари на 5*Q=480. По ова, бидејќи се решени половина од задачите, ученикот ќе оди на ФИНКИ, при што неговиот квалитет на решавање ќе се зголеми на Q=96 + 37 = 133.
Останува да се реши преостанатата задача, која го зголемува квалитетот на решавање на ученикот на Q=133 + 10 = 143. Кредибилитетот кај комисијата за натпревари до овој момент е 480, а по решавање на оваа задача ќе се зголеми за 4 * 143 = 572, и ќе изнесува 1052.