Algorithm

B. Businessmen Problems
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/981/problem/B
input
standard input
output
standard output

Two famous competing companies ChemForces and TopChemist decided to show their sets of recently discovered chemical elements on an exhibition. However they know that no element should be present in the sets of both companies.

In order to avoid this representatives of both companies decided to make an agreement on the sets the companies should present. The sets should be chosen in the way that maximizes the total income of the companies.

All elements are enumerated with integers. The ChemForces company has discovered n� distinct chemical elements with indices a1,a2,…,an�1,�2,…,��, and will get an income of xi�� Berland rubles if the i�-th element from this list is in the set of this company.

The TopChemist company discovered m� distinct chemical elements with indices b1,b2,…,bm�1,�2,…,��, and it will get an income of yj�� Berland rubles for including the j�-th element from this list to its set.

In other words, the first company can present any subset of elements from {a1,a2,…,an}{�1,�2,…,��} (possibly empty subset), the second company can present any subset of elements from {b1,b2,…,bm}{�1,�2,…,��} (possibly empty subset). There shouldn't be equal elements in the subsets.

Help the representatives select the sets in such a way that no element is presented in both sets and the total income is the maximum possible.

Input

The first line contains a single integer n� (1≤n≤1051≤�≤105)  — the number of elements discovered by ChemForces.

The i�-th of the next n� lines contains two integers ai�� and xi�� (1≤ai≤1091≤��≤109, 1≤xi≤1091≤��≤109)  — the index of the i�-th element and the income of its usage on the exhibition. It is guaranteed that all ai�� are distinct.

The next line contains a single integer m� (1≤m≤1051≤�≤105)  — the number of chemicals invented by TopChemist.

The j�-th of the next m� lines contains two integers bj�� and yj��, (1≤bj≤1091≤��≤109, 1≤yj≤1091≤��≤109)  — the index of the j�-th element and the income of its usage on the exhibition. It is guaranteed that all bj�� are distinct.

Output

Print the maximum total income you can obtain by choosing the sets for both companies in such a way that no element is presented in both sets.

Examples
input
Copy
3
1 2
7 2
3 10
4
1 4
2 4
3 4
4 4
output
Copy
24
input
Copy
1
1000000000 239
3
14 15
92 65
35 89
output
Copy
408
Note

In the first example ChemForces can choose the set (3,73,7), while TopChemist can choose (1,2,41,2,4). This way the total income is (10+2)+(4+4+4)=24(10+2)+(4+4+4)=24.

In the second example ChemForces can choose the only element 109109, while TopChemist can choose (14,92,3514,92,35). This way the total income is (239)+(15+65+89)=408(239)+(15+65+89)=408.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e5 + 1;
int n, m;
map<int, int> a, b;
vector<int> all;

int main() {
  scanf("%d", &n);
  for(int i = 0, x, y; i < n; ++i) {
  	scanf("%d %d", &x, &y);
  	a[x] = y;
  	all.push_back(x);
  }

	scanf("%d", &m);
  for(int i = 0, x, y; i < m; ++i) {
  	scanf("%d %d", &x, &y);
  	b[x] = y;
  	all.push_back(x);
  }

  sort(all.begin(), all.end());
  all.resize(unique(all.begin(), all.end()) - all.begin());

  long long res = 0;
  for(int i = 0, mx; i < all.size(); ++i) {
  	mx = 0;
  	if(a.count(all[i]))
  		mx = max(mx, a[all[i]]);
  	if(b.count(all[i]))
  		mx = max(mx, b[all[i]]);
  	res += mx;
  }

  printf("%lld\n", res);

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
1 2
7 2
3 10
4
1 4
2 4
3 4
4 4

Output

x
–
+
cmd
24
Advertisements

Demonstration

Codeforces Solution-B. Businessmen Problems-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+