D. Bessie and Infinite Dungeon
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie is trapped in an infinite dungeon and must fight a repeating sequence of bosses until she is eventually defeated. Throughout her journey, she has accumulated coins. A line of heroes is willing to fight for her, each for a price.

There are $$$N$$$ bosses, numbered $$$1, 2, \ldots, N$$$. Boss $$$i$$$ has health $$$H_i$$$ and deals $$$D_i$$$ damage. Bessie fights bosses in order. After boss $$$N$$$ is defeated, the sequence starts again from boss $$$1$$$.

There are $$$M$$$ heroes, in a fixed order. Hero $$$j$$$ has health $$$h_j$$$, damage $$$d_j$$$, and cost $$$c_j$$$. Bessie starts with $$$C$$$ coins.

For each hero in order, Bessie may either:

  • hire them if she can afford their cost, paying $$$c_j$$$ coins, or
  • skip them forever.

If Bessie hires a hero, they immediately fight the current boss. Combat proceeds in rounds:

  1. The boss attacks first, reducing the hero's health by its damage.
  2. If the hero is still alive, the hero attacks and deals damage to the boss.

If a hero's health drops to $$$0$$$ or below, they die and are gone forever. If a boss's health drops to $$$0$$$ or below, that boss is defeated and the hero leaves immediately; heroes never continue onto the next boss.

Bessie plays optimally; that is, she make choices that will allow her to deal as much damage as possible.

Note that any excess damage dealt beyond a boss's remaining HP is discarded — overkill does not count nor carry over.

Input

The first line contains three positive integers $$$N$$$, $$$M$$$, and $$$C$$$ ($$$1 \le N \le 10^6$$$, $$$1 \le M \le 5000$$$, $$$0 \le C \le 5000$$$).

The next $$$N$$$ lines contain $$$H_i$$$ and $$$D_i$$$ ($$$1 \le H_i \le 10^9$$$, $$$0 \le D_i \le 10^9$$$).

The next $$$M$$$ lines contain $$$h_j$$$, $$$d_j$$$, and $$$c_j$$$. ($$$1 \le h_j, d_j \le 10^9$$$, $$$0 \le c_j \le 5000$$$).

Output

Print two space-separated integers:

  • the damage already dealt to the current boss when Bessie dies
  • the total damage dealt to all bosses.
Examples
Input
3 5 5
10 2
1 0
8 3
5 4 3
3 2 2
3 9 0
6 2 2
1 1 9
Output
0 11
Input
1 3 2
20 100
50 3 0
101 7 1
101 7 1
Output
14 14
Note

In the first sample, the most optimal strategy is to hire Hero $$$1$$$ for $$$3$$$ coins, dealing $$$8$$$ damage on Boss $$$1$$$. Then, skip Hero $$$2$$$ and hire Hero $$$3$$$ for $$$0$$$ coins, defeating Boss $$$1$$$ (the $$$9$$$ damage is capped to $$$2$$$). Bessie hires Hero $$$4$$$, who then deals $$$1$$$ damage to Boss $$$2$$$ and defeats it. After Hero $$$4$$$ leaves, Bessie is left with Hero $$$5$$$, which is too expensive to hire, thereby forcing us to skip and get defeated. The total damage dealt sums up to $$$11$$$, and no damage is dealt to Boss $$$4$$$.

Another optimal strategy is to hire Hero $$$1$$$, Hero $$$2$$$, and Hero $$$3$$$. We are forced to skip Hero $$$4$$$ and Hero $$$5$$$. This strategy also sums up to $$$11$$$ damage dealt to bosses.