Street Food Delight

There is a vibrant street food market with n shops arranged from left to right and numbered starting from 1. The i-th shop offers a unique snack with calorie value \(h_i\) and tastiness \(w_i\). There are m foodies, each having a query. The i-th foodie will consider shops in the interval \([l_i, r_i]\) and has a maximum calorie allowance of \(t_i\). Each shop's snack can be eaten at most once. For each query, determine the maximum total tastiness the foodie can achieve without exceeding the calorie limit.

This problem can be modeled as a 0/1 knapsack problem on a subarray. For each query, you are given a list of items (shops) in the range \([l_i, r_i]\) with the calorie cost \(h_i\) and value \(w_i\), and you need to select a subset whose total calories do not exceed \(t_i\) while maximizing the total tastiness.

inputFormat

The first line contains two integers n and m representing the number of shops and the number of queries.

The second line contains n integers \(h_1, h_2, ..., h_n\), where \(h_i\) represents the calorie value of the snack at the i-th shop.

The third line contains n integers \(w_1, w_2, ..., w_n\), where \(w_i\) represents the tastiness of the snack at the i-th shop.

Then m lines follow, each containing three integers l_i, r_i and t_i, indicating that the i-th foodie will consider the shops from index l_i to r_i (inclusive) and has a maximum calorie limit of t_i.

outputFormat

For each query, print one line containing a single integer: the maximum total tastiness that can be achieved without exceeding the calorie limit.

sample

5 3
2 4 1 3 5
3 5 2 6 4
1 3 3
2 5 7
1 5 10

5
11
16