28 lines
929 B
Python
28 lines
929 B
Python
# PARTIEL BUG #
|
|
# Mauvaise réponse sur le test 2
|
|
# Complexité: O(k*n*log(n)), cela ne semble pas être le problème (ou pas encore)
|
|
# l'idée est de trier à chaque fois pour trouver l'élément qui, en prenant en compte les k_-1 réductions qu'il va offrir, coûtera le moins cher
|
|
|
|
def find_best(k):
|
|
return lambda x: x[0]-(k-1)*x[1]
|
|
|
|
def main():
|
|
n, k = map(int, input().split())
|
|
discos = [tuple(map(int, input().split())) for _ in range(n)]
|
|
|
|
balance = 0
|
|
total_discount = 0
|
|
for k_ in range(k, 0, -1):
|
|
if len(discos) == 0:
|
|
exit(1)
|
|
# On cherche celui qui rapportera le plus (/coûtera le moins)
|
|
discos.sort(key=find_best(k_))
|
|
# On prend en compte combien il nous fait gagner
|
|
balance -= discos[0][0]
|
|
total_discount += discos[0][1]*(k_-1)
|
|
del discos[0]
|
|
|
|
return -(balance+total_discount)
|
|
|
|
for _ in range(int(input())):
|
|
print(main()) |