Akatsuki vs Leaf
Tag(s):

## Bitmask, Dynamic Programming, Easy-Medium, Matching

Problem
Editorial
Analytics

Akatsuki is planning to attack the Leaf Village to capture Naruto. The Hokage ( Head of the Village ), came to know about the plan and also the number of members, N, in Akatsuki who are going to attack. So, Hokage planned an ambush.

Hokage selected a team of N members ( one for each Akatsuki member ) and named it Leaf. Each member of Leaf can attack exactly one Akatsuki member and an Akatsuki member is NOT attacked by more than one Leaf member. In the ambush there will be N fights ( one of each N members of Leaf and N members of Akatsuki ). You are the leader of Leaf. You know the positions ( x-coordinates and y-coordinates ) of all the Akatsuki members and Leaf members. Your task is to assign each member of Leaf to exactly one member of Akatsuki team such that the sum of the distance between them is minimum. Distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ will be equal to $|x_1 - x_2| + |y_1 - y_2|$.

Input:
First line contains one integer N, number of Akatsuki members who are going to attack the village.
Next N lines will contain two integers each, X and Y, x-coordinate and y-coordinate of the Akatsuki members.
Next N lines will contain two integers each, X and Y, x-coordinate and y-coordinate of the Leaf members.

Output:
Print the required minimum sum of the distance.

Constraints:
$1 \le N \le 20$
$-10^6 \le X, Y \le 10^6$

SAMPLE INPUT
2
0 0
8 8
1 1
6 6

SAMPLE OUTPUT
6

Explanation

$N = 2$
So there are 2 Akatsuki members at position $(0, 0)$ and $(8, 8)$ and 2 Leaf members at position $(1, 1)$ and $(6, 6)$. There are 2 cases:
Case 1:
Leaf member at $(1, 1)$ will fight Akatsuki member at $(0, 0)$ and Leaf member at $(6, 6)$ will fight Akatsuki member at $(8, 8)$.
Sum of distances = $((|1-0| + |1-0|) + (|6-8| + |6-8|)) = (2 + 4) = 6$

Case 2:
Leaf member at $(1, 1)$ will fight Akatsuki member at $(8, 8)$ and Leaf member at $(6, 6)$ will fight Akatsuki member at $(0, 0)$.
Sum of distances = $((|1-8| + |1-8|) + (|6-0| + |6-0|)) = (14 + 12) = 26$

So Case 1 is optimal and minimum sum of distances is 6.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

June Circuits

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Algorithms > Dynamic Programming