eolymp
bolt
Try our new interface for solving problems
Məsələlər

Прием на работу

Прием на работу

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Вам необходимо нанять работников для строительного проекта. Заявление о приёме на работу подали n кандидатов, пронумерованных от 1 до n включительно. Каждый кандидат с номером k требует, чтобы в случае приёма его на работу ему платили не менее чем S_k долларов. Также для каждого кандидата с номером k известен его уровень квалификации Q_k. Положение о строительной деятельности требует, чтобы вы платили работникам пропорционально их уровню квалификации относительно друг друга. Например, если вы нанимаете двух работников A и B таких что Q_A = 3 * Q_B, то вы обязаны платить работнику A ровно в три раза больше, чем вы платите работнику B. Вам разрешается платить работникам нецелое число денег. Более того, разрешается даже платить количество денег, которое не может быть записано с помощью конечного числа десятичных цифр, такое как треть или шестую долю доллара.

В вашем распоряжении есть w долларов, и вы хотите нанять как можно больше рабочих. Вы решаете кого нанимать и сколько им платить, но вы должны удовлетворить как требованиям работников о минимальном жаловании, так и требованиям положения о строительной деятельности. Естественно, что вам требуется уложиться в бюджет, равный w долларам.

Для данного строительного проекта уровень квалификации работников не имеет значения. Вы заинтересованы только в том, чтобы нанять как можно больше работников независимо от их уровня квалификации. Однако, если есть несколько способов достичь цели, то вы хотите выбрать такой, чтобы общая сумма денег, которую вы заплатите работникам, была как можно меньше. Если и этого можно достичь несколькими способами, то нет никакого различия между этими способами, и вас удовлетворит любой из них.

Напишите программу, которая по заданным требованиям к жалованию и уровням квалификации кандидатов, а также количеству денег, которое у вас есть, определяет, каких кандидатов вам требуется нанять. Вы должны нанять как можно больше из них и при этом потратить как можно меньше денег, соблюдая требования положения о строительной деятельности, описанные выше.

Giriş verilənləri

Первая строка содержит два целых числа n(1 ≤ n ≤ 500 000) и w(1 ≤ w ≤ 10^{10}), разделённые пробелом. Следующие n строк описывают кандидатов, по одному кандидату на каждую строку. k-я строка из них описывает кандидата с номером k и содержит два целых числа S_k и Q_k(1 ≤ S_k, Q_k ≤ 20 000), разделённых пробелом.

Максимальное значение w не может быть представлено 32-битным типом данных. Вам необходимо использовать 64-битный тип данных, такой как long long в C/C++ или int64 в Pascal, чтобы значение w можно было сохранить в одной переменной. Дополнительные подробности представлены на страницах с технической информацией.

Çıxış verilənləri

Первая строка должна содержать одно целое число h – количество работников, которых вы принимаете на работу. Следующие h строк должны содержать список номеров кандидатов в произвольном порядке, которых вы выбрали для найма на работу (различные целые числа от 1 до n), по одному в каждой строке.

Nümunə

Giriş verilənləri #1
4 100
5 1000
10 100
8 10
20 1
Çıxış verilənləri #1
2
2
3