Seeds
At the market, there is a row of N spots where sunflower seeds are sold. Potential buyers walk along this row, eventually stopping to purchase seeds. While the quality of seeds is consistent across spots, the price and location vary.
Before entering the market as a new seed seller, you conducted research to understand how the number of buyers depends on these factors. The research revealed that most buyers follow a similar pattern: they pass by several spots, noting the prices, and after passing K spots, they return to the spot with the lowest price they noticed and make a purchase there. If multiple spots have the same price, the buyer chooses the closest one.
For example, consider five spots with prices 37, 34, 34, 35, 33. If a buyer with K = 4 moves from left to right, they see prices 37, 34, 34, 35. They then decide to return to the third spot to buy seeds, as it offers the lowest price within their range. Although the second spot has the same price, it is further away. If the same buyer starts from the right, they see prices 33, 35, 34, 34, and return to the fifth spot.
The number of spots a buyer passes before deciding (K) depends on their greed and patience, varying among buyers. The research provides the average percentage B_K of buyers for each K (1 ≤ K ≤ N, 0 ≤ B_K ≤ 99, with the sum of all B_K equaling 100).
Your task is to determine the optimal strategy for placing a new spot in this market to maximize expected average profit. Assume half of the customers walk from the first spot to the N-th, and the other half from the N-th to the first, following the described pattern.
Input
The first line contains the number of existing spots N. The second line lists N integers representing the prices at each spot. The third line contains N integers ranging from 0 to 99, representing the values of B_K for each K (2 ≤ N ≤ 100, with prices being integers from 1 to 9999). All numbers are separated by spaces.
Output
Output two integers: L and P. L (0 < L < N) is the position after which the new spot should be placed (you cannot place your spot first or last). P is the optimal price. If multiple optimal solutions exist, choose the one with the smallest L, and among those, the smallest P.