chooseEmployee

Công ty ABC đang thiếu nhân lực trầm trọng, họ muốn tuyển k nhân viên vào công ty trong số danh sách ứng cử viên cho trước, mỗi ứng cử viên chỉ có 1 kỹ năng và mức lương cần phải trả trong 1 năm. Đối với ứng cử viên thứ i, kỹ năng của người này sẽ là skill[i] và mức lương phải trả là salary[i].

Nhưng mọi chuyện không đơn giản như vậy. Công ty yêu cầu ứng cử viên họ tuyển vào phải có kỹ năng requestSkill cho trước. Nếu trong tất cả các nhân viên không ai có kỹ năng này hoặc nếu chưa tuyển đủ k nhân viên, công ty sẽ ưu tiên tuyển từ ứng cử viên mang trong mình kỹ năng có độ thịnh hành từ cao nhất tới thấp nhất

Hãy cho biết tổng tiền lương nhỏ nhất có thể mà công ty ABC cần phải trả cho k nhân viên vừa tuyển trong 1 năm, nếu như không thể tuyển đủ số lượng nhân viên yêu cầu, trả về -1.

Lưu ý: Kỹ năng thịnh hành nhất là giá trị được lặp lại nhiều nhất trong danh sách skill, nếu có nhiều hơn 2 kỹ năng lặp lại với số lần bằng nhau, độ thịnh hành sẽ được sắp từ cao đến thấp theo tên aphabet của skill (a->b->c->…).

Ví dụ:

• Với skill=["Java",".Net","C++","Java"], salary=[20,40,60,80] , requestSkill=".Net" và k=3 thì chooseEmployee(skill,salary,requestSkill,k)=120
• Giải thích
  • Chọn 1 ứng cử viên có kỹ năng ".Net" -> result=0+40=40
  • Vì chưa đủ k=3 ứng cử viên, chọn tiếp ứng cử viên có kỹ năng "Java" vì độ thịnh hành của nó lớn nhất, kỹ năng này có 2 ứng cử viên -> result=40+20+80=140

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

• [Đầu vào]

  • Array Of Strings: skill[]  0 ≤ skill.size() ≤ 105            0 ≤ skill[i].size()<15
  • Array Of Integer: salary[]  salary.size() = skill.size() 0 ≤ salary[i] ≤ 1000
  • String: requestSkill (Công ty có thể yêu cầu bất kỳ kỹ năng nào). 0 ≤ requestSkill.size()<15
  • Integer: k  0 ≤ k ≤ 105

• [Đầu ra] Integer
  Số lương nhỏ nhất công ty phải trả, nếu không tuyển đủ số nhân viên, trả về -1.