Maximum Beauty of a Stable Tower

You are given n cubic blocks. The i-th block has side length a_i and pattern type w_i.

A tower is a sequence of blocks represented by indices p₁, p₂, \dots, p_m (all indices are distinct). The tower is said to be stable if the side lengths are strictly decreasing:

$$a_{p_1} > a_{p_2} > \dots > a_{p_m}.$$

The beauty of a tower is defined as the sum of the blocks' side lengths minus a penalty applied for every pair of adjacent blocks with different patterns. In particular, given a positive integer c, the beauty is defined as:

$$\sum_{i=1}^{m}a_{p_i} - c\cdot\sum_{i=1}^{m-1}[w_{p_i}\neq w_{p_{i+1}}], $$

where the indicator function \([w_{p_i}\neq w_{p_{i+1}}]\) is 1 if \(w_{p_i}\neq w_{p_{i+1}}\) and 0 otherwise.

Your task is to choose a subset of blocks and arrange them in a stable tower so that the beauty is maximized. Output the maximum beauty achievable.

inputFormat

The input consists of three lines:

• The first line contains two integers n and c (the number of blocks and the penalty coefficient).
• The second line contains n integers: a₁, a₂, ..., a_n representing the side lengths of the blocks.
• The third line contains n tokens: w₁, w₂, ..., w_n representing the pattern type of each block. The tokens may be strings or characters.

You can assume that n is at least 1.

outputFormat

Output a single integer representing the maximum beauty of a stable tower that can be constructed.

sample

3 2
5 3 2
1 1 2

8