有n个整数排成一排，有一些数字被固定在某些位置，另外的一些可以自由交换。超能侠想要使所有相邻两数乘积的和最大，请你帮帮他。

第一行输入一个整数 $(1 \le n \le 16)$。

接下来n行，每行给出两个整数$a_i(−10^4 \le a_i \le 10^4)、p_i(-1 \le p_i \lt n)$，以空格分割。

$a_i$表示数字的值，$p_i$​为该数字指定的位置，如果$p_i = −1$，代表该数字的位置不被限制。输入保证不会为两个数字指定相同的位置。

数字重新排列后最大的所有相邻两数乘积的和，即$\max \{a_1*a_2+a_2*a_3+......+a_{n−1} * a_n \}$。