ECOO '20 P2 - Online Shopping

View as PDF

Submit solution

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

Problem type

Like many others, Mimi has spent the last month practicing social distancing. As part of her efforts, she has started shopping entirely online. She's found that online shopping offers a lot of advantages. In particular, you can easily look at many different websites in order to find the best price for an item.

However, others have also started shopping online, which means that stores are running out of inventory. As a result, Mimi often has to order from multiple websites in order to get all the items that she wants.

Mimi has a number of items that she has to buy. Can you help Mimi determine the minimum amount of money that she needs to spend to buy all the items?

Input Specification

The first line begins with a single integer T (1 \le T \le 10), the number of test cases. T test cases follow.

Each test case begins with one integer N (1 \le N \le 100), the number of stores. N store descriptions follow. Each store description begins with an integer M (1 \le M \le 100), the number of different items sold at each store. The next M lines each contain a lower-case string S and two integers P, Q (1 \le P, Q \le 100): the name of an item, its price, and the quantity that the store has in stock. Each item's name will be unique, and contain at most 50 characters.

The next line contains an integer K (1 \le K \le 100), the number of different items that Mimi would like to buy. The next K lines each contain an item name S and an integer D (1 \le D \le 100), the amount of that item that Mimi would like to buy. Each item's name will only appear at most once.

It is guaranteed that, unlike the real world, the total quantity of each item available in stores is greater than or equal to the quantity that Mimi would like to buy.

Output Specification

For each test case, print a single integer: the minimum amount that Mimi needs to spend to buy all the items that she wants.

Sample Input

toiletpaper 1 50
catnip 2 25
toiletpaper 100 1
toiletpaper 51
catnip 10

Sample Output


Educational Computing Organization of Ontario - statements, test data and other materials can be found at


There are no comments at the moment.