给定一组物品,每种物品都有自己的重量和价值,且每种最多选取一件。在限定的总重量内,该如何选择,才能使得物品的总价值最高。
第一行两个整数,为物品数量和限定重量。
接下来行,每行两个整数,为物品重量和价值。
仅一个整数,为答案。
4 6 1 4 2 5 3 6 4 7
15
3 199999999999998 99999999999999 50000000000000 99999999999999 50000000000000 100000000000000 99999999999999
100000000000000
20 105463152304571546 7170405446104555 8541685161274992 5921992294379980 8046340357650005 2815915138156125 8964490643596980 9046003330274729 1584098999655528 408955439391956 1440027954914981 3268497337723536 9617730032520013 9625779259838677 8661077383429250 5660958626651601 8913681894953851 3136147631208476 4836541979403419 1018140449176111 2965306079969471 4136076694702358 7130859844581335 112305811825252 7272947738702007 3445736365004136 5907826561952303 8929462444399517 2453084942219608 7806952673428582 9442281004521776 8759999215593466 9621433948708713 1619844784526748 4254400629992061 1824596355133712 1882890014203142 5608666707882825 2747144315124299 8325056612549222 476803688675357
114760653176049091