Problem : 265 - Hiring

Special Judge

Problem Statistics

Solved Member: 15　　Submission: 64　　User Tried: 15

Statement:

你需要從N個工人中僱用一些工人。每個工人期望的最低工資為S_k美元，技術等級是Q_k。建築工業法規要求僱用的工人中支付給每個工人的工資與他的技術等級成正比，並且滿足他們期望的最低工資。舉例來說，假如你雇用兩位工人A與B，而且Q_A = 3*Q_B，那麼你必須付給工人A正好三倍於工人B的工資。你可以付給你的工人非整數的工資。這甚至包括在十進位數字中無法以有限位數表示的金額，例如三分之一或六分之一元。

你手上有W美元，而且你希望能僱傭盡可能多的工人。你可以決定僱用的對象以及他們的工資，但是必須滿足你所僱用的工人們的最低工資要求，同時必須遵守工業法規。並且總預算不超過W美元。

你的專案在本質上是完全和資格等級無關，因此你只需要最大化工人的人數，而不需要考慮他們的資格等級。然而，如果有多種方案，你應該選擇一種方式使得你必須付的總工資最低，如果仍有多種，輸出任意一種方案即可。

Task:

給定應徵者不同的工資需求、資格等級以及你的預算，請寫一個程式，決定你應該僱用那些應徵者。

你必須儘可能的僱用更多的工人，並且使用較少的預算，同時還要遵守前述的工業法規。

Input:Output:

第一行包含整數N和W，以空白隔開。

接下來的N行描述這些應徵者的資訊，其中第k行描述編號為k的應徵者，包含以空白隔開的整數S_k與Q_k

範圍限制：
1 ≤ N ≤ 500000，應徵者個數。
1 ≤ S_k ≤ 20000，編號為k的應徵者的最小工資需求。
1 ≤ Q_k ≤ 20000，編號為k的應徵者的資格等級。
1 ≤ W ≤ 10¹⁰，你的預算金額。

佔50分的測試資料中，N不超過5000。

第一行輸出H，表示你所僱用的工人數量。

接下來的H行列出你決定僱用的應徵者編號（每位應徵者都有同的編號，從1到N），每行一個編號，任意順序皆可。

Sample Input:Sample Output:

Sample #1:
4 100
5 1000
10 100
8 10
20 1

Sample #2:
3 4
1 2
1 3
1 3

Sample #3:
3 40
10 1
10 2
10 3

Sample #1:
2
2
3

Sample #2:
3
1
2
3

Sample #3:
2
2
3

HINT:

Sample 1:
你唯一負擔的起同時僱用兩位應徵者且滿足全部限制條件的方法是僱用2號與3號的應徵者。你必須分別支付他們80元和8元的工資，因此合乎100元的預算。

Sample 2:
在這個例子中，你負擔的起僱用所有三位應徵者，你付給1,2,3號應徵者1元, 1.5元, 1.5元，成功的在你的4元預算內僱用每個應徵者。

Sample 3:
這裡你負擔不起僱用所有三位應徵者，因為他們會花掉你60元，但是你可以僱用其中兩位。你選擇僱用2與3號，因為跟其他僱用兩位應徵者的組合相比，這個組合會花掉你最少的工資總和。你可以付2號10元和3號15元，總共25元。假如你僱用1號和2號，你需要分別付他們至少10元和20元。假如你僱用1號和3號，那麼你需要分別付給他們10元和30元。

Source:

IOI 2009

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	3000ms	65536kb
0-2	3000ms	65536kb
0-3	3000ms	65536kb
1	3000ms	65536kb	2
2	3000ms	65536kb	2
3	3000ms	65536kb	2
4	3000ms	65536kb	2
5	3000ms	65536kb	2
6	3000ms	65536kb	2
7	3000ms	65536kb	2
8	3000ms	65536kb	2
9	3000ms	65536kb	2
10	3000ms	65536kb	2
11	3000ms	65536kb	2
12	3000ms	65536kb	2
13	3000ms	65536kb	2
14	3000ms	65536kb	2
15	3000ms	65536kb	2
16	3000ms	65536kb	2
17	3000ms	65536kb	2
18	3000ms	65536kb	2
19	3000ms	65536kb	2
20	3000ms	65536kb	2
21	3000ms	65536kb	2
22	3000ms	65536kb	2
23	3000ms	65536kb	2
24	3000ms	65536kb	2
25	3000ms	65536kb	2
26	3000ms	65536kb	2
27	3000ms	65536kb	2
28	3000ms	65536kb	2
29	3000ms	65536kb	2
30	3000ms	65536kb	3
31	3000ms	65536kb	3
32	3000ms	65536kb	3
33	3000ms	65536kb	3
34	3000ms	65536kb	3
35	3000ms	65536kb	3
36	3000ms	65536kb	3
37	3000ms	65536kb	3
38	3000ms	65536kb	3
39	3000ms	65536kb	3
40	3000ms	65536kb	3
41	3000ms	65536kb	3
42	3000ms	65536kb	3
43	3000ms	65536kb	3