Minimum Deletion Cost to Reduce Longest Increasing Subsequence

Given a sequence (A), where each element (A_i) has a deletion cost (B_i) and an additional attribute (C_i). You are allowed to delete some elements so that the length of the longest increasing subsequence (LIS) of the remaining sequence is at most (L-1), where (L) is the length of the LIS of the original sequence. The goal is to minimize the total deletion cost.

If there are multiple optimal solutions, output the one where the sorted list of the deleted elements' attributes (i.e. the sorted sequence of (C_i) for the removed items) is lexicographically smallest.

All formulas are given in LaTeX format.

inputFormat

The input consists of four lines:\

1. The first line contains a single integer (n) ((1 \le n \le 20)), the length of the sequence.\
2. The second line contains (n) space-separated integers representing the sequence (A).\
3. The third line contains (n) space-separated integers representing the deletion costs (B).\
4. The fourth line contains (n) space-separated strings representing the additional attributes (C) for each element.

outputFormat

Output a single line containing the sorted additional attributes (separated by a single space) of the deleted elements that achieve a reduction in the LIS (by at least 1) with minimal total deletion cost. If multiple solutions exist, output the lexicographically smallest one.

sample

5
1 2 3 4 5
5 4 3 2 1
a b c d e

a