A radio dial has M positions numbered 0 to M - 1 arranged in a circle, so position M - 1 is next to position 0. There are n receivers; receiver i is tuned to position pos[i] and retuning it costs w[i] per step. One step moves a receiver to a neighbouring position, in either direction.
You must pick one integer target position t (with 0 <= t < M) and retune every receiver to t, each along its shorter way round. The distance between positions a and b is min(|a - b|, M - |a - b|), and the total cost is the sum of w[i] * distance(pos[i], t).
Return the minimum possible total cost.
Examples
Input: M = 100, pos = [10, 20, 45], w = [1, 1, 1]
Output: 35
Explanation: t = 20 costs 10 + 0 + 25.
Input: M = 12, pos = [0, 3, 5], w = [5, 1, 2]
Output: 13
Explanation: t = 0 costs 0 + 3*1 + 5*2.
Constraints
1 <= M <= 10**91 <= n = len(pos) = len(w) <= 10**50 <= pos[i] < M; several receivers may share a position1 <= w[i] <= 10**4- Large tests have
n = 10**5andMup to10**9, so trying every position or every pair of receivers is far too slow.
Goals
- Minimise a weighted sum of distances measured around a circle
- Prove which candidate targets can be optimal and test only those
- Evaluate every candidate in O(1) with prefix sums and a moving boundary