SPOJ.com - Problem IQTEAM

IQTEAM - IQ Team

no tags

In Byteland we can study only math and IT.

In the university there are n math students and m IT students.

Rector Byteasar knows IQ of every student. He wants to make the best team, which would solve the hardest human being problems. So he decided to pick team with the highest summary IQ.

Of course it's not everything. He wants to make team in which each student knows another students from team.

Every student from IT know other student from IT and same with math students.

Help him finding team with the largest summary IQ and in which every student from team knows another students from team.

Input

In first line n, m, k (0 < n ≤ 400, 0 < m ≤ 400, 0 ≤ k ≤ n × m) which means number of math students, number of IT students, number of friendships between IT and math student.

In next k lines pairs

0 < ai ≤ n, 0 < bi ≤ m, which means ai student from math knows bi student from IT.

In next line n numbers, IQ of i-th math student.

In next line m numbers, IQ of i-th IT student.

Output

Output in one line : number of team's summary IQ.

Example

Input:
3 2 3
1 1
2 1
2 2
1 3 1
1 2

Output:
6

Submit solution!

hide comments



	Shaka Shadows: 2013-08-12 13:22:28 Regarding constraints, I have assumed this: - all IQ values are within range [0, 10^9].
	Miguel Oliveira: 2011-11-20 19:51:26 well, the bipartite graph is clear, we have to find the best "sort of" clique in this graph. However, i continue to have no reasonable idea of how to do this. I thought about exploring the complement graph to find the maximum independent set, but with the values on the nodes (iq's) this doesn't seem to help. I don't see how to apply any of the graph algorithms i know here. Can you elaborate a bit more? If it is too much of a spoiler, you may e-mail me (e-mail in my profile). Thanks Last edit: 2011-11-20 19:53:08
	Douglas Ferlini Bastos Machado[UNB]: 2011-11-19 20:29:13 do you mean O((n+m)^C)?
	[Rampage] Blue.Mary: 2011-11-16 02:21:23 This is NOT a searching problem, at least for me. I've found some algorithm with polynomial running time, i.e. O((n+m)^C) where C is a constant <=5. Last edit: 2011-11-20 13:27:11
	Miguel Oliveira: 2011-11-15 18:13:22 Can anyone give a hint? Do we need to use a particular algorithm or this is a more general search problem? I tried to check the friendship intersection of every pair of math students and, for each one, find the other math students that know the same it students (using bitmasks to make this fast enough). I got WA and now I think that this approach is probably incorrect. However, I'm not able to find another solution Last edit: 2011-11-15 18:16:14
	:-P: 2011-11-10 14:12:09 -"which every student knows another students from team." I don't get it ! Does it mean (another student) or (other students) or (all the other students) ?? I think according to the example every student knows (all the other students) Last edit: 2011-11-11 14:34:08
	Miguel Oliveira: 2011-11-10 14:12:09 Thank you for your answers. I corrected my code but still have WA. Is there any tricky case you may share? I don't know if my approach is incorrect or I have a bug..
	Krzysztof Lewko: 2011-11-10 14:12:09 @Miguel: long long is required to solve this problem. -yes IQ of every student is not negative -yes one team can be done work only math or IT students
	1377448: 2011-11-10 14:12:09 i'm having wrong answer too... it seems to work to me :S damn found where i was wrong Last edit: 2011-11-09 21:36:35
	Miguel Oliveira: 2011-11-10 14:12:09 This is an interesting problem :) I'm having wrong answer. I would like to know: - the result fits in a signed 32 bit integer? - is IQ always > 0? - can the team be made only from math or only from it students? I supposed yes to all Last edit: 2011-11-09 19:54:07

Submit solution!

Added by:	Krzysztof Lewko
Date:	2011-11-09
Time limit:	0.100s-1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	AMPPZ 2011