This page is still under construction.

Parts of this page are still being built. What you see may change.

Boat Berthing

Time limit2sMemory limit512 MB

Summary
Boats arrive in order and each takes the leftmost empty dock whose capacity fits its length; report the sum of boat index times dock index at the end.
Level

Medium7 of 10

Topics
Segment tree, Binary search, Greedy, Array
Solved
No attempts yet

Problem

Albert runs a boat berthing station along a lakeshore.

The station has n small docks, numbered 1 to n from left to right. Dock i can be used to berth a boat whose length is at most P[i]. Each dock holds at most one boat. Today, m boats will enter the station in order (numbered 1 to m in the order they enter). The j-th boat has length B[j].

Each boat berths at a dock or passes through the station according to the following rules.

  1. Each boat enters from the left and moves to the right. If there is an empty dock where the boat can berth, it berths there. (For example, if dock i is empty and P[i] ≥ B[j], then the j-th boat can berth at dock i.)
  2. If there is no dock where the boat can berth, it leaves without berthing.

For example, let n = 3, m = 5, P = [2, 2, 2], B = [1, 2, 3, 2, 1] (see the figure below).

The boats pass through the station in order as follows.

  • Boat 1, with length 1, berths at dock 1. (see the left figure)
  • Boat 2, with length 2, berths at dock 2 because dock 1 is not empty. (see the middle figure)
  • Boat 3, with length 3, cannot berth because the boat is too long, even though dock 3 is empty, so it passes through the station.
  • Boat 4, with length 2, berths at dock 3. (see the right figure)
  • Boat 5, with length 1, passes through the station.

After every boat has berthed or left the station, let A[i] be the number of the boat berthed at dock i. If no boat is berthed there, A[i] = 0.

Albert wants to know the value of A[1] × 1 + A[2] × 2 + ... + A[n] × n. Help Albert compute this value. For the example above, A = [1, 2, 4] after the last boat leaves the station, so the answer is 17.

Input

The first line gives the number of test cases T.

Each test case is given over three lines.

The first line gives n and m, separated by a space.

The second line gives n integers (P[1], ..., P[n]), separated by spaces.

The third line gives m integers (B[1], ..., B[m]), separated by spaces.

Output

For each test case, print the answer on its own line.

Constraints

  • 1 ≤ T ≤ 3
  • 1 ≤ n, m ≤ 200,000
  • 1 ≤ P[i], B[j] ≤ 9 × 10^18

Examples2

  1. Example 1

    Input
    2
3 5
2 2 2
1 2 3 2 1
5 5
1 2 1 2 1
2 1 2 1 2
    Expected output
    17
28

  2. Example 2

    Input
    2
5 6
15 15 15 20 20
20 10 20 10 20 100
5 6
1 2 3 2 1
100 3 2 1 2 3
    Expected output
    29
36