Submission #73211819

---

Source Code Expand

def solve():
    # Read number of items and coupon limit
    n, k = map(int, input().split())
    
    # Store items with their savings (regular_price - sale_price)
    items = []
    for _ in range(n):
        regular_price, sale_price = map(int, input().split())
        savings = regular_price - sale_price
        items.append((savings, regular_price, sale_price))
    
    # Sort by savings in descending order (greedy: maximize total savings)
    items.sort(reverse=True)
    
    # Calculate minimum total cost
    total_cost = 0
    
    # Use coupon on top k items (items with largest savings)
    for i in range(min(k, n)):
        total_cost += items[i][2]  # Add sale price
    
    # Buy remaining items at regular price
    for i in range(min(k, n), n):
        total_cost += items[i][1]  # Add regular price
    
    print(total_cost)

# Run the solution
solve()

Submission Info

Judge Result