Optimal Apartment Rental
You are looking for an apartment and have a list of available apartments, each with a specific rent and a specific distance from your work. You want to rent an apartment such that the total cost, which is the sum of its rent and its distance from work multiplied by a factor K, is minimized. You are allowed to choose any apartment. Find the minimum possible total cost.
Input
The first line contains two integers N and K, where N is the number of apartments and K is the cost factor. The next N lines each contain two integers, the rent and the distance of an apartment.
Output
Print a single integer, the minimum possible total cost.
Constraints
1 <= N <= 200000 1 <= K <= 1000 1 <= rent, distance <= 100000
Example 1
3 2 10 5 20 3 15 7
20
Apartment 1: 10 + 5*2 = 20. Apartment 2: 20 + 3*2 = 26. Apartment 3: 15 + 7*2 = 29. Minimum is 20.
Example 2
2 10 100 1 10 2
30
Apartment 1: 100 + 1*10 = 110. Apartment 2: 10 + 2*10 = 30. Minimum is 30.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 2 10 5 20 3 15 7
2 10 100 1 10 2