Problem D. Recruitment

# Problem D. Recruitment ### Source - [hihoCoder](http://hihocoder.com/contest/mstest2015april/problem/4) ### Problem 鏃堕棿闄愬埗:10000ms 鍗曠偣鏃堕檺:1000ms 鍐呭瓨闄愬埗:256MB ### 鎻忚堪 A company plans to recruit some new employees. There are N candidates (indexedfrom 1 to N) have taken the recruitment examination. After the examination,the well-estimated ability value as well as the expected salary per year ofeach candidate is collected by the Human Resource Department. Now the company need to choose their new employees according to these data. Tomaximize the company's benefits, some principles should be followed: 1. There should be exactly X males and Y females. 2. The sum of salaries per year of the chosen candidates should not exceedthe given budget B. 3. The sum of ability values of the chosen candidates should be maximum,without breaking the previous principles. Based on this, the sum of the salaryper year should be minimum. 4. If there are multiple answers, choose the lexicographically smallest one.In other words, you should minimize the smallest index of the chosencandidates; If there are still multiple answers, then minimize the secondsmallest index; If still multiple answers, then minimize the third smallestone; ... Your task is to help the company choose the new employees from thosecandidates. ### 杈撳叆 The first line contains four integers N, X, Y, and B, separated by a singlespace. The meanings of all these variables are showed in the descriptionabove. 1 <= N <= 100, 0 <= X <= N, 0 <= Y <= N, 1 <= X +Y <= N, 1 <= B <= 1000. Then follows N lines. The i-th line contains the data of the i-th candidate: acharacter G, and two integers V and S, separated by a single space. Gindicates the gender (either "M" for male, or "F" for female), V is the well-estimated ability value and S is the expected salary per year of thiscandidate. 1 <= V <= 10000, 0 <= S <= 10. We assure that there is always at least one possible answer. ### 杈撳嚭 On the first line, output the sum of ability values and the sum of salariesper year of the chosen candidates, separated by a single space. On the second line, output the indexes of the chosen candidates in ascendingorder, separated by a single space. 鏍蜂緥杈撳叆 ~~~ 4 1 1 10 F 2 3 M 7 6 M 3 2 F 9 9 ~~~ 鏍蜂緥杈撳嚭 ~~~ 9 9 1 2 ~~~