Fractional Knapsack (Կոտորակային պարկ)
Տրված են
n իրեր (յուրաքանչյուրը ունի սեփական քաշ և արժեք), ինչպես նաև Ձեր տրամադրության տակ էcapacity W ունեցող պարկ: Պահանջվում է պարկի մեջ տեղադրել ընտրած իրերի (կամ դրանց մասերի) այնպիսի տարբերակ, որ ստացվի առավելագույն ընդհանուր արժեք: Կ Allowed է վերցնել յուրաքանչյուր իրից միայն որոշակի կոտորակ (մասնակի բաժին), և համապատասխանաբար արժեքը համամասնորեն փոխվում է վերցված բաժնի չափին:Ո՞րն է պարկի առավելագույն ընդհանուր արժեքը:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n (1 ≤ n ≤ ) և W (1 ≤ W ≤ ), որոնք համապատասխանաբար իրերի քանակն են և պարկի տարողունակությունը:Հաջորդ
n տողերից յուրաքանչյուրում տրված են բացատով բաժանված δύο ամբողջ թվեր (1 ≤ , ≤ ), որոնք համապատասխանաբար իրի քաշն ու արժեքն են:Ելք
Ծրագիրը ելքում պետք է տպի պարկի առավելագույն ընդհանուր արժեքը:
Օրինակներ
Мուտք | Ելք |
3 50
10 60
20 100
30 120 | 240 |
4 60
40 280
10 100
20 120
24 120 | 440 |
Պարզաբանում
- 60 + 100 + (2/3)120 = 240
- 280 + 100 + (10/20)120 = 440
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB