409332: GYM103485 N Game Show

You are the leader of a team with $$$N$$$ members in a game show. One of the games, "Collect what you can", is played by a few members of the team, one player at a time, and consists of going to a store with $$$K$$$ items, each with a weight of $$$wi_i$$$ and a value of $$$v_i$$$. Each team member is able to carry a maximum total weight of $$$c_i$$$ within the game's time limit and wants to maximize the sum of the values of the items carried. Each team member also has its own weight $$$wp_i$$$ and the members who participate in this task must all first enter an elevator with total weight capacity $$$L$$$, that is, the sum of the weights of the chosen members must be less than or equal to $$$L$$$. As the team leader your task is to choose a subset of members that will fit in the elevator and maximize the sum of collected items. The game is played independently by each of the chosen members, that is, the $$$K$$$ items in the store reset for each member to play. What is the maximum possible sum of collected item's values your team can get?

The first line contains 3 integers $$$N$$$, $$$K$$$ and $$$L$$$ ($$$1 \leq N,K \leq 100$$$, $$$1 \leq L \leq 10000$$$), the number of members of your team, the number of items in the store and the elevator's weight limit. The following $$$N$$$ lines each contain a pair of integers $$$c_i$$$, $$$wp_i$$$ ($$$1 \leq c_i, wp_i \leq 10000$$$) that represent the carrying capacity and weight of each member of your team. The following $$$K$$$ lines each contain two integers $$$wi_i$$$ and $$$v_i$$$ ($$$1 \leq wi_i, v_i \leq 10000$$$) the weight and value of each item.

Print a single integer, the maximum possible sum of collected items your team members can get from the store such that the sum of these members' weights is less than or equal to $$$L$$$.

3 3 10
3 5
4 5
6 5
4 10
2 8
2 1

28

Explanation of Example 1: As the elevator capacity is $$$10$$$ and the weight of each person is $$$5$$$, we can only choose $$$2$$$ people. If we choose the person $$$2$$$, who takes the item $$$1$$$, and the person $$$3$$$, who takes the items $$$1$$$ and $$$2$$$, we get a total value of $$$10 + 18 = $$$28