Spaceship Engine Vector Optimization

Commander XiaoSheng is in charge of the spaceship Shenzhou 100 during its navigation mission. The spaceship is equipped with n engines that produce horizontal thrust. The i-th engine outputs a horizontal velocity vector \(\overrightarrow{p_i}=(x_i,y_i)\). Note that the spaceship does not rotate during the travel.

You are required to solve the following three problems:

1. Directional Component: When the engines are activated in some combination, the resulting velocity is the vector sum of the chosen engines. For a given direction vector \(\overrightarrow{q}=(x_q,y_q)\), the component of the overall velocity in the \(q\) direction is the projection onto \(\overrightarrow{q}\). In order to avoid handling floating point issues with unit vectors, output the product of the maximum achievable component and \(|\overrightarrow{q}|\) (where \(|\overrightarrow{q}|=\sqrt{x_q^2+y_q^2}\)). In other words, if you choose a subset \(S\) of engines so that the component of \(\sum_{i\in S} \overrightarrow{p_i}\) in the \(q\) direction is maximized, then output \[ \left( \max_{S\subseteq\{1,2,\cdots,n\}}\frac{\overrightarrow{q}}{|\overrightarrow{q}|}\cdot\sum_{i\in S}\overrightarrow{p_i} \right)\cdot |\overrightarrow{q}| = \max_{S\subseteq\{1,2,\cdots,n\}} \overrightarrow{q}\cdot\sum_{i\in S}\overrightarrow{p_i}. \]
   (Hint: simply choose those engines that contribute a positive dot product with \(\overrightarrow{q}\)).

2. Maximum Speed: By selecting an arbitrary subset of engines (possibly empty), the spaceship's velocity is the vector sum. Output the square of the maximum possible speed, that is, if \(\mathbf{v}\) is the resulting sum then output \(|\mathbf{v}|^2\).

3. Exactly k Engines: Among all subsets containing exactly \(k\) engines, output the square of the maximum achievable speed, i.e. the maximum \(|\sum_{i\in S} \overrightarrow{p_i}|^2\) when \(|S|=k\).

Input/Output note: For problems 2 and 3, output the squared speed, while for problem 1, output the dot product as explained.

inputFormat

The input consists of several lines:

• The first line contains an integer \(n\) \((1\le n\le 20)\), the number of engines.
• The next \(n\) lines each contain two integers \(x_i\) and \(y_i\), representing the components of \(\overrightarrow{p_i}\).
• The following line contains two integers \(x_q\) and \(y_q\), representing the components of the direction vector \(\overrightarrow{q}\). \(\overrightarrow{q}\) is not the zero vector.
• The last line contains an integer \(k\) \((0\le k\le n)\), used for problem 3.

All numbers are separated by spaces.

outputFormat

Output three lines containing the answers to the three problems:

1. For problem 1, output the maximum "partial speed" multiplied by \(|\overrightarrow{q}|\) (i.e. the maximum dot product accumulated).
2. For problem 2, output the square of the maximum achievable speed.
3. For problem 3, output the square of the maximum speed achievable by using exactly \(k\) engines.

It is guaranteed that the answers are integers.

sample

3
1 2
-2 3
3 -1
1 0
2

4
26
26