The potatoes of the oppressed potato farms under Jiahai the mayor have decided to stage a revolution against the tyranny of Jiahai, and to overthrow Jiahai to form the Republic of Potatoes. All the potatoes have been called upon to serve their fellow potatoes by exchanging whatever they had for ammunition, and to use the ammunition in the battle against Jiahai.
The potato farm has N potatoes, each of them with a different item (e.g. "Apple" or "Root") There are V vending machines situated around the farm that can exchange a certain item for another item (e.g. an apple for an orange) However, each vending machine takes a certain amount of time to use, and the potatoes don't have much time!
Given the original amount of time and the original item each potato has, determine how many potatoes will be able to exchange for ammunition on time and join the revolution if they use the vending machines optimally and assuming many potatoes can use the vending machine at the same time.
The first line of input contains two integers, N
The next V
lines of input contains two strings and one integer each, representing a vending machine, with the first string being the item this vending machine accepts, the second string being the item that this vending machine returns, and the integer being how long it takes to run this vending machine.
The next N
lines of input contain one string and one integer each, representing a potato, with the string being the item the potato has at the beginning and the integer representing how much time the potato has.
Your output should contain one integer, the maximum number of potatoes that can join the revolution.
All strings will be ≤ 10 characters long and the time required to operate each vending machine ≤ 1000.
Subtask 1 (15%): 1 ≤ N, V ≤ 100.
Subtask 2 (35%): 1 ≤ N, V ≤ 1 000.
Subtask 3 (50%): 1 ≤ N, V ≤ 100 000.
Subtask 4 (0%): As per sample testcases.
Sample Input 1
apple orange 2
apple banana 3
orange ammunition 5
Sample Output 1
Explanation for Sample 1
Potato 1 can exchange an apple for an orange in 2 time. To exchange for ammunition he needs 5 time. However he only has 6 time in total, so this is not possible.
Potato 2 can exchange an orange for the ammunition in 5 time. So he can join the revolution.
So in total 1 potato can join the revolution.