Albert는 앞으로 n개의 숙제를 해야한다 (편의상 1번부터 n번까지 번호가 붙어있다).

현재 시각은 S 이고, i번째 숙제의 내용은 정해진 시각 t[i]에 공개 된다 (어떤 숙제는 이미 공개 되었지만 Albert가 아직 제출 하지 않았을 수 있다). 각 숙제별로 벌점이 있어서, 만약 Albert가 i번째 숙제를 제출한 시각이 y[i] 라면 (y[i] - t[i]) × v[i] 만큼의 벌점이 부여된다.

숙제는 어렵지 않아서 모든 숙제는 내용이 공개 되는 즉시 풀어서 제출할 수 있지만, 숙제를 하나 제출하고나면 반드시 최소한의 휴식을 취해야 한다. Albert가 취할 수 있는 최소한의 휴식은 "1 단위 시간" 이다 (필요하다면 더 많이 쉬는 것도 가능하다).

예를 들어 n = 5, S = 3, t = [1, 2, 3, 4, 5], 그리고 v = [8, 3, 2, 13, 3]이라 하자.

• 숙제를 순서대로 할 경우, 각 숙제를 제출한 시각은 y = [3, 4, 5, 6, 7]이 된다 (현재 시각이 3임에 유의하자). 이 경우, 총 벌점은 2 × 8 + 2 × 3 + 2 × 2 + 2 × 13 + 2 × 3 = 58 이다.
• 숙제를 1, 4, 2, 5, 3번 순서로 할 경우, 각 숙제를 제출한 시각은 y = [3, 5, 7, 4, 6]이 된다. 이 경우, 총 벌점은 2 × 8 + 3 × 3 + 4 × 2 + 0 × 13 + 1 × 3 = 36 이다.
• 숙제를 1, 5, 4, 3, 2 순서대로 할 경우, 각 숙제를 제출한 시각은 y = [3, 8, 7, 6, 5]이 된다. 이때, 숙제 1을 시각 3에 제출하고 숙제 5가 공개될 때 까지 "2 단위 시간" 만큼 휴식한다. 이 경우, 총 벌점은 2 × 8 + 6 × 3 + 4 × 2 + 2 × 13 + 0 × 3 = 42 이다.

이 예제에서 두 번째 방법이 벌점을 최소화 하는 방법이다.

Albert가 모든 숙제를 다 제출하면서 달성 가능한 최소한의 벌점이 몇점인지 구해보자.

입력 형식

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 세 줄에 걸쳐 주어진다.

첫 줄에 두 정수 n과 S가 공백으로 구분되어 주어진다.

둘째 줄에 숙제가 언제 나오는지 나타내는 n개의 정수가 (t[1], ..., t[n]) 공백으로 구분되어 주어진다.

셋째 줄에 숙제의 벌점을 나타내는 n개의 정수가 (v[1], ..., v[n]) 공백으로 구분되어 주어진다.

출력 형식

각 테스트 케이스의 정답인 최소 벌점을 각 줄에 출력한다.

예제 입력

2
5 3
1 2 3 4 5
8 3 2 13 3
5 30
10 20 30 40 50
8 3 2 13 3

예제 출력

36
197