Employees Assignment

The manager of a company is required to complete in projects, where the number of employees required and the bonus reward earned by the manager for the project are represented by the arrays max employees[i] and bonus[i].

There is an array current_employees, that represents the number of employees that are assigned to the ith project currently. Initially, only one employee is assigned to each project. So. current employees[i]=1, for all 0 <= i < n. Now, the manager has m days to assign some employees to some projects. Each day the manager can do the following operation (may not perform any operation):

Choose any positive integer x and any project
Increase

the current employeestilto current employees(1) floor(current employees[i]/x) where floorfinum) is the largest integer less than or equal to num.

After mdays, a project x is said to be complete if current employees[x] = max employees[x/and the manager earns bonus[x/ amount of money for that project. The total bonus earned by the manager is the sum of bonus of all the complete projects after m days.

Given n projects, m days, and two arrays max_employees and bonus, find the maximum possible total bonus that can be earned by the manager after m days.

Example
Given n = 4, m = 4, max_employees = [1, 7, 5, 21, and bonus = [2, 6, 5, 2].
One of the optimal ways is explained below:

After m days, current employees-[1, 1.5, 2). Here we have projects at indices 0, 2, and 3 completed.

Hence the total bonus is bonus[0]+ bonus[2] + bonus(3)-2+5+2-9.

Function Description

Complete the function getMaxBonus in the editor below
getMaxBonus takes the following arguments:

int max employees[n]: the number of employees required for the projects
int bonus[n]: the bonus earned by the manager for completing the projects
int m: the number of days

Returns
Int: the maximum possible total_bonus that can be earned by the manager after m days

Constraints
• 1 <= n <= 10
• 1 <= max employees[i] ≤ 103
• 1 <= bonus[i] <= 10^6
0<m<10^6

Sample Input For Custom Testing

STDIN

FUNCTION

3

→

max_employees [] size n

= 3

6

→

max_employees = [6,

23, 3]

23

3

3

←

A bonus [] size n = 3 bonus = [100, 35, 39]

100

35

39

7

m = 7

Sample Output

139

Explanation

28

Choose x = 1 and set current_employees[0] = 1 + floor(1/1) = 2.

29

4

Again choose x = 1 and set current_employees[0] = 2 + floor(2/1) = 4.

3

5

Choose x = 2 and set current_employees[0] = 4 + floor(4/2) = 6.

6

Now, choose x = 1 and set current_employees[2] = 1 + floor(1 / 1) = 2.

Now choose x = 2 and set current_employees[2] = 2 + floor(2/2) = 3.

7

Only two days are left now, and 1 cannot be made equal to max_employees[1] = 23 in just two days.

8

Hence the total_bonus is 100+ 39 = 139.

Sample Case 1

Sample Input For Custom Testing

STDIN

FUNCTION

3

max_employees [] size n

2

→

= 3

max_employees = [3 5

3

→

2]

B

5

2

3

bonus [] size n = 3

7

bonus = [7,3,5]

←

3

5

2

→

→

k = 2

Sample Output

7

Explanation

Set current_employees[0] = 1 + floor(1 / 1) = 2 and then current_employees[0] = 2 + floor(2/ 2) = 3 with x = 1 and x = 2 respectively.

No more operations are left now and current_employees = [3, 1, 1].

Hence the total_bonus is 7.