Any ideas how to solve potentially DP problem?

Once at atcoder I've got the problem which listed bellow. I suppose that it's a DP problem. I have some ideas how to solve it - but I'm not sure that my approach leads to correct answer in any case.

Original problem D — 積の総和/SumTotal of product Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB

Question There are N empty cells in a grid that are aligned horizontally in one line and N numbers A1, A2, …, AN.

The goal is to organize the integers in A1, A2, …, AN to maximize S, where S represents of the sum of the products of all adjacent pairs of numbers.

Some cells may have already been assigned an integer value and cannot be changed.

Your program should output the maximum value of S.

When representing the index for the number that is assigned to the i(1≦i≦N)th cell from the left as Ii, S could be represented as: S=AI1×AI2+AI2×AI3+…++AIN−1×AIN.

Input The input will be given in the following format on Standard Input

N
A1 D1
A2 D2
:
AN D3

On the 1st line, integer N(1≦N≦16) is given. From 2nd line to Nth line, information regarding each number is given. The ith line contains the value of the ith integer Ai(−100≦Ai≦100) and an integer Di(1≦Di≦N or Di=−1). If Ai has not yet been assigned a cell, Di=−1. Otherwise, the Di represents the cell to which the integer has been assigned. Specifically, when Di≦0, it indicates that Ai is assigned to Dith cell from the left. Multiple numbers will not be assigned to the same cell. Output On the 1st line, the maximum value of S should be output.

Ensure that there is a line break following S.

Input Example #1
5
10 -1
20 -1
50 -1
40 -1
30 -1
Output1 Example 1#
4600

For example, if assigning each cell 10, 30, 50, 40, 20 from the left, it becomes 10×30+30×50+50×40+40×20=4600, which is the maximum value one can achieve.

Input Example #2
6
10 3
20 -1
50 -1
40 -1
30 -1
60 6
Output Example #2
6300

Some ideas:

1. Sort input sequence. It's intuitive that max product is possible only taking the product of 2 max elements in array.

2. Calculate all possible products of sequence - it's O(n^2) and store them in dict with key (idx[a1],idx[a2]) and the amount of prodcuts will be (n-1)^2

3. sort products in decreasing order.

4. start taking products from the top and placing them in resulting array, keeping track of already used products, and also the fact that each entry from original sequence could be used only 2 times in products. In case all allowed products are already taken - remove rest products from dict which include exausted item.

5. The most trick part for me is how to place items in resulting list? in case resulting array is empty the best place to put 2 items is the middle of array - since we have place to put other items either to the left or right. And this strategy needs traking of amount of free space at each of the borders.

but how to work out where to place elemenets in case when we have prepopulated array????: - stands for empty cell [-,-,-,50,-,-,20,-,-]

May be I should think about this problem in different way? Any ideas are welcome! Hope that this problem is as interesting for you as for me.