MTHUR - grace marks

no tags 

In earlier days , grading  in  BITS  used to be absolute , instead of relative grading scheme .
Once Professor Mathur decided to conduct a surprise quiz, and many students were caught unaware of it. 
Their scores of the students came out to be much worse than the previous years scores.


Professor Mathur really believed that true test of talent comes in difficult situations and continued such horrifying sequences of tests . But finally poor placements of his students turned the heat up for the professor and he decided to revise everyone's marks .
 
Now being a qualified mathematician , professor mathur applied a simple strategy to this.
He decided to award some constant grace marks to each and every student.
He took every students last year marks and then added up the absolute difference with the
revised current year marks  . And he decided to choose the grace marks with the least sum of absolute difference .
ie. sum( abs (a[i] - (b[i]+grace) )  ) should be minimum .
Also , prof. Mathur had a knack of choosing the grace value from his very set of favourite numbers .


Now that our students are happily placed in  'Microsoft' , 'Adobe' for the good Cool, credit finally goes to professor "mathur" .
Now , decide for each input ,what grace marks were given by mathur .
(if there are many such grace marks , choose the lowest one) .

Input

First line , t for number of testcases. Next 5*t line for each testcase .
First line of every testcase : integer n.
Second line : n integers showing previous years marks of every student .
Third line : n integers showing present years marks of every student .
Fourth line : intger m
Fifth line : m integers showing the possible values for grace marks

Output

Output the expected grace marks .

Example

Input:
1
5
9 10 7 3 10
4 1 4 1 3
6
0 1 2 3 4 5

Output: 5

contraints :
number of testcases , t < 20
maximum number of students : n < 10000
1 <= m,marks[i] <= 50000

hide comments
Archit Jain: 2016-02-27 21:46:32

Make sure in case of equal cost return the one with minimum grace marks added.
- :( Costed many wa's

Ankit: 2015-09-22 18:59:11

first question on unimodal function, :)

Akshat Mathur: 2015-06-30 16:43:47

AC after 9 WA & 1 RTE........!
Nice Question, learnt a new thing :-)

vikas sharma: 2013-06-20 21:14:02

AC...:)
one < costed me hell lot of TLE's...!!!

Abhishek: 2013-05-31 22:15:35

(if there are many such grace marks , choose the lowest one) . -> caused 2 WA's

Dario Pavlovic: 2012-10-31 21:54:03

Grace marks are sorted? They have to be?

Naman: 2012-10-14 20:48:59

@Gaurav- reset your variables lsum,ls for each test case. Avoid using same loop variables(i here) for inner and outer loops. Your algo is O(n*m) which will be TLE probably

@Romal- Grace marks are supposed to be positive right? and hence the last set of m numbers will have positive numbers only?

Last edit: 2012-10-15 16:24:14
Gaurav Khewal: 2012-10-02 07:17:34

@Romal Thoppilan
http://ideone.com/clone/yh2RA
it is giving right answer on ideone but wrong on spoj
can u tell me the eror in this code

Romal Thoppilan: 2012-10-02 00:33:15

then choose the mminimum of such grace values.

Gaurav Khewal: 2012-10-02 00:33:15

@Romal Thoppilan IS IT POSSIBLE THAT WE CAN HAVE SAME SUM FOR TWO GRACE VALUES???

Last edit: 2012-10-01 19:42:55

Added by:Romal Thoppilan
Date:2012-08-20
Time limit:0.620s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PERL6 PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:own problem