Maximum Hamiltonian Cycle in a Directed Graph

Given n tuples \((a_i, b_i)\) for \(1 \le i \le n\), construct a complete directed graph \(G\) with n nodes, where the weight of the edge from node \(i\) to node \(j\) is defined as \(|a_i-b_j|\). A Hamiltonian cycle is a cycle that visits every vertex exactly once and returns to the starting vertex. The task is to find a Hamiltonian cycle in \(G\) such that the total weight, i.e., the sum of \( |a_{p_i}-b_{p_{i+1}}| \) over the cycle (with \(p_{n+1}=p_1\)), is maximized. Output this maximum sum.

The mathematical formulation is as follows:

For a permutation \(p\) of \(\{1,2,\dots,n\}\) forming a Hamiltonian cycle, the objective is to maximize \[ S = \sum_{i=1}^{n} \left|a_{p_i} - b_{p_{i+1}}\right| \quad \text{with} \quad p_{n+1} = p_1. \]

inputFormat

The input begins with a line containing a single integer (n) ((2 \le n \le 16)), representing the number of tuples. Each of the following (n) lines contains two integers (a_i) and (b_i), separated by a space.

outputFormat

Output a single integer, denoting the maximum sum of the weights along a Hamiltonian cycle.

sample

2
1 100
100 1

0