← 返回 bloomberg 的题目列表Minimum Cost to Send People to Two Cities (Generalized to K)
类型：online_judge
Problem: Minimum Cost to Send People to SF and NY (Generalized to K)
You are given n people (for Part 1, n is even). Each person can travel either to San Francisco (SF) or New York (NY). For person i, the cost to go to SF is costs[i][0] and the cost to go to NY is costs[i][1].
Part 1
Compute the minimum total cost such that:
exactly n/2 people go to SF
exactly n/2 people go to NY
Part 2 (Follow-up)
Given an integer k (0 <= k <= n), compute the minimum total cost such that:
exactly k people go to SF
the remaining n-k people go to NY
Input format (stdin)
First line: two integers n and k (for Part 1 you may set k = n/2)
Next n lines: two integers cost_sf cost_ny
Output format (stdout)
Output one integer: the minimum total cost under the constraint
Constraints
n is even (Part 1)
1 <= n <= 2000 (reasonable interview-scale; provide an implementable solution)
0 <= k <= n (Part 2)
0 <= cost_sf, cost_ny <= 10^4
Sample tests
Test 1
Input:
4 2
10 20
30 200
400 50
30 20
Output:
110
Test 2
Input:
2 1
10 100
20 30
Output:
40
Test 3 (k=0)
Input:
3 0
5 6
1 100
10 2
Output:
108
Test 4 (k=n)
Input:
3 3
5 6
1 100
10 2
Output:
16
Test 5 (large deltas)
Input:
6 3
1 1000
2 1000
3 1000
1000 1
1000 2
1000 3
Output:
12
Example
Input
4 2
10 20
30 200
400 50
30 20
Output
110