Being satisfied with Little Graphy’s performance, Big China Day says, “You already have the ability to be a good warrior.”
“I don’t have anything more to teach you. All you need to defeat those evil river crabs is faith.”
“Good luck, hare, maybe we’ll meet again in the future,” Big China Day waves his hand and starts his next journey.
After ten minutes of study, Little Graphy learns all the things Big China Day knows.
“Wow, it’s time to get our kidney…our Gobi back! Let’s roooooock!” Blues cheers.
“Calm down,” Little Graphy pulls Blues, “we still need something to bribe the guard of the Gobi Gate.”
“Ummm, You’re right. I’ll find out where Gobi is…” says Blues, acting as if he were The Thinker.
“Surely, you’re not listening to me…. Well, I might as well find a present myself,” sighs Little Graphy.
Entering a shop, she finds two queues of rabbit dolls. “I can’t imaginate how cute it would be if I combine these dolls!” Little Graphy thinks while pulling Blues, who is still acting The Thinker.
“Those guards will be too shocked to move if they see such a cute thing!” she says, “It’s god-like!!”
As a result, Little Graphy decides to make a tower of rabbit dolls.
Little Graphy can choose one doll from the front of the two queues each time. She may decide to keep or not to keep the doll each time she takes one doll. The dolls she keeps will be stacked onto the rabbit tower by the order she takes. It means that if the doll is the kth doll she keeps, it’ll be the kth doll if you count from the bottom.
Every rabbit doll has two values V, D. Any rabbit doll i in the tower, which has x dolls on top of it, will contributes Vi − x × Di points to the cuteness. In order to bribe the guard, Little Graphy wants to maximize the cuteness of the tower. Can you help her calculate the maximum value of cuteness?
The first line contains an integer T indicating the number of test case.
Each test case starts with two integers n, m. indicating the length of the two queues.
The following line contains n pairs of integers V, D representing the n rabbits in the first queue.
The next line contains m pairs of integers V, D representing the m rabbits in the second queue.
For each test case, print the maximum cuteness of the rabbit tower.