TLE '17 Contest 1 P2 - Willson and Food

View as PDF

Submit solution

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

Problem type
Pizza is one of Willson's favourite foods.

Willson the Canada Goose is like any other Canada goose - he likes to eat grass. But, as anyone knows, there are different types of grass (e.g. green, blue, white, corn). Additionally, some humans like to feed geese with other foodstuffs (e.g. bread, pizza, hot dogs).

Each food type can provide energy to Willson or drain it away if it's unhealthy. Willson's energy can become negative. Willson must use up one unit of energy in order to move one meter. Willson cannot move if he has zero or negative energy, but he can still eat. You know the energy values of F food types - the i^\text{th} food type is named s_i and has an energy value of e_i.

Willson sees N food items in front of him. The food type of j^\text{th} item is t_j and the item is located d_j meters away from Willson's initial location. Willson will eat any food item that he encounters.

How many food items can Willson eat?

Input Specification

The first line of input will contain F (1 \le F \le 10^3).

F lines of input will follow. The i^\text{th} line will contain a string s_i and an integer e_i. All s_i are pairwise unique.

The next line of input will contain N (1 \le N \le 10^3).

N lines of input will follow. The j^\text{th} line will contain a string t_j and an integer d_j (0 \le d_j \le 10^9). It is guaranteed that t_j is equal to some s_i.

All strings will be at most 10 characters long and will only contain lowercase English letters.

It is guaranteed that N \times \max |e_i| \le 10^9.

Output Specification

Output a single integer, the number of food items that Willson can eat.

Sample Input

grass 5
bread 10
metal -100
bread 5
grass 0
grass 6
bread 10
metal 9

Sample Output


Explanation for Sample Output

Willson first eats the 2^\text{nd} food item, providing him 5 energy. Just as he runs out of energy, he encounters the 1^\text{st} food item, which provides him 10 energy. He passes the 3^\text{rd} food item, providing him 5 more energy. However, he eats the 5^\text{th} food item, which completely drains all of his energy and leaves him unable to move.


There are no comments at the moment.