The Food
Limits: 2 sec., 256 MiB
There are \(N\) plates with food. Each plate is described by its food name and its weight. You want to take some of them, but you don’t want to have two plates with the same food (i.e. with the same food name). Find the maximal possible total weight of the food you can take.
Input
The first line contains the integer \(N\). Each of the following \(N\) lines contains a string \(S_j\) and an integer \(W_j\) separated with a single space. Here \(S_j\) is the name of the food on the \(j\)-th plate and \(W_j\) is the weight of the \(j\)-th plate.
Output
The only integer which is the maximal possible total food weight.
Constraints
\(1 \le N < 1000\),
\(1 \le W_j \le 1000\),
\(1 \le |S_j| \le 10\),
\(S_j\) contains only lowercase Latin letters.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 potato 4 soup 2 potato 9 steak 2 steak 5 potato 4 rice 1 | 17 |
Notes
You can take plates potato 9, soup 2,
steak 5 and rice 1.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|