Description

The only difference between easy and hard versions are constraints on q, a_i and b_i.

There are n items. The weight and value of the i-th item are w_i and v_i separately.

The total weight of items you can take away is at most m.

There are q queries. In each query, what is the maximum sum of value you can get if you must take the a_i-th item and b_i-th item?

Input

The first line contains two integers n, m (2 ≤ n ≤ 20, 0 ≤ m ≤ 10⁹) – the number of items and the totol weight you can take away.

Then n lines follow. The i+1-th line contains two integers w_i, v_i (0 ≤ w_i, v_i ≤ 10⁹) – the weight and value of the i-th item.

Next line contains one integer q (1 ≤ q ≤ 10⁵) – the times of the queries.

Then q lines follow. The i+n+2-th line contains two integers a_i, b_i (1 ≤ a_i < b_i ≤ n) – the two items you must take in the i-th query.

Output

For each query output the maximum sum of value you can get(if there is no legal plan, output 0 instead) and then output a newline('\n').

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss