Under construction

Still being built. Things may change

Criss-Cross Cables

Time limit2.5sMemory limit512 MB

Summary
Place m edges between n fixed points on a line with given lengths, reusing ports but with no repeated pair; say whether all m wires fit.
Level

Medium7 of 10

Topics
Greedy, Sorting, Math, Implementation
Solved
No attempts yet

Problem

As a participant in the BAPC (Bizarrely Awful Parties Competition) you are preparing for your next show. You do not know anything about music, so you rip off someone else's playlist and decide not to worry about that any more. What you do worry about is the aesthetics of your set-up: if it looks too simple, people will be unimpressed and they might figure out that you are actually a worthless DJ.

It does not take you long to come up with a correct and fast solution to this problem. You add a long strip with a couple of useless ports, and add some useless cables between these ports. Each of these cables connects two ports, and these special ports can be used more than once. Everyone looking at the massive tangle of wires will surely be in awe of your awesome DJ skills.

However, you do not want to connect the same two ports twice directly. If someone notices this, then they will immediately see that you are a fraud!

You have made a large strip, with the ports in certain fixed places, and you have found a set of cables with certain lengths that you find aesthetically pleasing. When you start trying to connect the cables, you run into another problem. If the cables are too short, you cannot use them to connect the ports! So you ask yourself the question whether you are able to fit all of the cords onto the strip or not. If not, the aesthetics are ruined, and you will have to start all over again.

Input

  • The first line has nn, the number of ports on the strip, and mm, the number of wires, with 2≤n≤5⋅1052 \le n \le 5 \cdot 10^5 and 1≤m≤5⋅1051 \le m \le 5 \cdot 10^5.
  • The second line has integers x1,…,xnx_1, \ldots, x_n, the positions of the nn sockets, with 0≤x1<⋯<xn≤1090 \le x_1 < \cdots < x_n \le 10^9.
  • The third line has mm integers l1,…,lml_1, \ldots, l_m, the lengths of the wires, with 1≤li≤1091 \le l_i \le 10^9.

Output

Print yes if it is possible to plug in all the wires, or no if this is not possible.

Examples2

  1. Example 1

    Input
    4 4
    0 2 3 7
    1 3 3 7
    
    Expected output
    yes
    
  2. Example 2

    Input
    3 4
    0 1 2
    10 10 10 10
    
    Expected output
    no