Sound System Testing
Alex has a collection of sound sources, each of which has a certain strength. Each of the sound sources can be heard up to a threshold distance. Alex stands on the x-axis at the origin, x = 0. Arrange the speakers at consecutive positive integral points, 1, 2, 3 and so on, to achieve the minimum sound strength at the origin. The sound strength at the origin is the sum of the strengths of all sound sources that can be heard there.
For example, suppose Alex has sound sources with strengths = [5, 10, 3, 2] and threshold_dist = [3, 3, 1, 1], respectively for each source. Two potential arrangements are presented below.
Given information:
[5, 10, 3, 2] - strengths
[3, 3, 1, 1] - threshold_dist
[1, 2, 3, 4] - original indices
Two Possible arrangements:
[3, 2, 4, 1] - First arrangement, indices rearranged
[1, 3, 1, 3] - threshold_dist arranged to indices above
[3, 10, 0, 0] - sound strengths
[1, 4, 3, 2] - Second arrangement, indices rearranged
[3, 1, 1, 3] - threshold_dist arranged to indices above
[5, 0, 0, 0] - sound strengths
In the first arrangement, sound source 3 is placed at the first position. Its threshold is 1 and it is 1 unit distance from Alex. Alex can hear the sound with a strength of 3. The sound reaches Alex with a total strength of 3 + 10 + 0 + 0 = 13. In the second arrangement, the total strength is 5 + 0 + 0 + 0 = 5. The second arrangement is minimal.
Function Description
Complete the function minStrength in the editor below. The function must return a long integer denoting the minimum sound strength possible.
minStrength has two parameters -
strengths: an integer array
threshold_dist: an integer array
Input Format
The first line contains a single integer , the number of sound sources Alex has.
Next line contains space-separated integers denoting the strengths of the sources.
Next line contains space-separated integers denoting the thershold distances of the sources.
Constraints
- _
Output Format
Output a single number, the minimum total sound strength Alex can achieve in arranging the sound sources at consecutive positive integral points along the x-axis. There is a code stub to handle I/O if you choose to use it.
Sample Input 0
3
1 2 3
5 10 15
Sample Output 0
6
Explanation 0
No matter in what order Alex places the sources, sound can be heard from all of them.
Sample Input 1
4
2 3 2 2 5
2 3 4 5 5
Sample Output 1
4
Explanation 1
Alex can place the sources in the order [3 4 1 2 5] to get a total strength of 4. Note that [4 3 2 1 5] also results in the same total strength.