//v / wが大きいほうから詰めていく嘘貪欲(もちろんWA) #include #include #include using namespace std; struct Baggage { double key; long long v, w; Baggage() {} Baggage(long long v, long long w) { this->v = v; this->w = w; key = (double)v / w; } bool operator>(const Baggage &r) const { return key > r.key; } }; int n; long long w; Baggage bag[5000]; int main() { int i; cin >> n >> w; for (i = 0; i < n; i++) { long long v, w; cin >> v >> w; bag[i] = Baggage(v, w); } sort(bag, bag + n, greater()); long long remW = w; long long sumV = 0; for (i = 0; i < n; i++) { if (remW >= bag[i].w) { remW -= bag[i].w; sumV += bag[i].v; } } cout << sumV << endl; return 0; }