- Practice
- Data Structures
- Advanced
- Subsequence Weighting

# Subsequence Weighting

# Subsequence Weighting

A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence.

You are given a sequence `A`

in which every element is a pair of integers i.e `A`

= *[(a _{1}, w_{1}), (a_{2}, w_{2}),..., (a_{N}, w_{N})]*.

For a subseqence `B`

= *[(b _{1}, v_{1}), (b_{2}, v_{2}), ...., (b_{M}, v_{M})]* of the given sequence :

- We call it increasing if for every
*i*(1 <=*i*<*M*) ,*b*._{i}< b_{i+1} *Weight(B) = v*._{1}+ v_{2}+ ... + v_{M}

**Task:**

Given a sequence, output the maximum weight formed by an increasing subsequence.

**Input:**

The first line of input contains a single integer *T*. *T* test-cases follow. The first line of each test-case contains an integer *N*. The next line contains *a _{1}, a_{2} ,... , a_{N}* separated by a single space. The next line contains

*w*separated by a single space.

_{1}, w_{2}, ..., w_{N}**Output:**

For each test-case output a single integer: The maximum weight of increasing subsequences of the given sequence.

**Constraints:**

1 <= *T* <= 5

1 <= *N* <= 150000

1 <= *a _{i}* <= 10

^{9}, where

*i ∈ [1..N]*

1 <=

*w*<= 10

_{i}^{9}, where

*i ∈ [1..N]*

**Sample Input:**

```
2
4
1 2 3 4
10 20 30 40
8
1 2 3 4 1 2 3 4
10 20 30 40 15 15 15 50
```

**Sample Output:**

```
100
110
```

**Explanation:**

In the first sequence, the maximum size increasing subsequence is 4, and there's only one of them. We choose `B = [(1, 10), (2, 20), (3, 30), (4, 40)]`

, and we have `Weight(B) = 100`

.

In the second sequence, the maximum size increasing subsequence is still 4, but there are now 5 possible subsequences:

```
1 2 3 4
10 20 30 40
1 2 3 4
10 20 30 50
1 2 3 4
10 20 15 50
1 2 3 4
10 15 15 50
1 2 3 4
15 15 15 50
```

Of those, the one with the greatest weight is `B = [(1, 10), (2, 20), (3, 30), (4, 50)]`

, with `Weight(B) = 110`

.

Please note that this is not the maximum weight generated from picking the highest value element of each index. That value, 115, comes from [(1, 15), (2, 20), (3, 30), (4, 50)], which is not a valid subsequence because it cannot be created by only deleting elements in the original sequence.