<s> """<STR_LIT>""" <EOL> MOD = <NUM_LIT:10> ** <NUM_LIT:9> + <NUM_LIT:7> <EOL> __author__ = '<STR_LIT>' <EOL> class Cost ( object ) : <EOL> def __init__ ( self ) : <EOL> self . cost = <NUM_LIT:0> <EOL> def __iadd__ ( self , other ) : <EOL> self . cost = ( self . cost + other % MOD ) % MOD <EOL> return self <EOL> class Solution ( object ) : <EOL> def solve ( self , cipher ) : <EOL> """<STR_LIT>""" <EOL> M , N , Y , X = cipher <EOL> y = list ( Y ) <EOL> x = list ( X ) <EOL> y . sort ( ) <EOL> x . sort ( ) <EOL> cost = Cost ( ) <EOL> while x and y : <EOL> x_max = x [ - <NUM_LIT:1> ] <EOL> y_max = y [ - <NUM_LIT:1> ] <EOL> if x_max > y_max : <EOL> cost += x . pop ( ) * ( M - len ( y ) ) <EOL> elif y_max > x_max : <EOL> cost += y . pop ( ) * ( N - len ( x ) ) <EOL> else : <EOL> if sum ( x ) > sum ( y ) : <EOL> cost += x . pop ( ) * ( M - len ( y ) ) <EOL> else : <EOL> cost += y . pop ( ) * ( N - len ( x ) ) <EOL> while x : <EOL> cost += x . pop ( ) * ( M - len ( y ) ) <EOL> while y : <EOL> cost += y . pop ( ) * ( N - len ( x ) ) <EOL> return cost . cost <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> import sys <EOL> f = open ( "<STR_LIT>" , "<STR_LIT:r>" ) <EOL> testcases = int ( f . readline ( ) . strip ( ) ) <EOL> for t in xrange ( testcases ) : <EOL> M , N = map ( int , f . readline ( ) . strip ( ) . split ( "<STR_LIT:U+0020>" ) ) <EOL> Y = map ( int , f . readline ( ) . strip ( ) . split ( "<STR_LIT:U+0020>" ) ) <EOL> X = map ( int , f . readline ( ) . strip ( ) . split ( "<STR_LIT:U+0020>" ) ) <EOL> cipher = [ M , N , Y , X ] <EOL> s = "<STR_LIT>" % ( Solution ( ) . solve ( cipher ) ) <EOL> print s , </s>
