숙제

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])가 공백으로 구분되어 주어진다.

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

• 1 ≤ T ≤ 10
• 1 ≤ n ≤ 100,000
• 1 ≤ S ≤ 2,000,000,000
• 1 ≤ t[i] ≤ 2,000,000,000
• 1 ≤ v[i] ≤ 40,000