SGS Programming Challenge P4 - Toy in Psychology Class

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Andy is exploring how toys impact a person's happiness level in his psychology class. He recruited a study participant named Jamie.

Jamie can select N toys from the store to be his birthday gifts, and he can exchange toys with his friends. There are M types of toys.

For the i^\text{th} toy (1 \le i \le M), Jamie can select at most S_i of it from the store, and it has a base happiness value of H_i. However, if Jamie owns multiple of the same toy, the happiness value Jamie gets from it decreases: the second toy will only give him \frac{1}{2} of H_i happiness, the third toy will give him \frac{1}{3} of H_i happiness, and the S_i^\text{th} toy will give him \frac{1}{S_i} of H_i happiness. Note that if the happiness value is a decimal, it will be rounded down to the nearest integer.

Jamie has K friends. His i^\text{th} friend, where 1 \le i \le K, has an infinite amount of toy B_i and is willing to exchange one of his toy B_i with one of Jamie's toy A_i, but Jamie will lose D_i happiness in the process. It is worth noting that Jamie can refuse an exchange or repeat an exchange as many times as he wants as long as he has the appropriate toy for exchange.

You need to find the maximum amount of happiness Jamie can achieve after some (possibly zero) exchanges.


For all subtasks:

1 \le N \le 1\,000

1 \le M \le 100

0 \le K \le 100

0 \le S_i \le 100

1 \le H_i, D_i \le 10^6

1 \le A_i, B_i \le M

Subtask 1 [15%]

K = 0

Subtask 2 [85%]

No additional constraints.

Input Specification

The first line contains three integers N, M, and K.

The following M lines contain two integers H_i and S_i.

The following K lines contain three integers A_i, B_i, and D_i.

Output Specification

Output an integer that represents the maximum sum of happiness value Jamie can achieve.

Sample Input

4 5 2
100 1
20 2
30 1
200 0
10 4
5 4 150
3 2 5

Sample Output


Sample Explanation

Jamie selects one of each toy 1, 2, 3, 5 from the store and exchanges his toy 5 with his first friend's toy 4.


There are no comments at the moment.