Problem A
Criss-Cross Cables

Picture by Oliver Quinlan.

As a participant in the BAPC (Bizarrely Awful Parties Competition) you are preparing for your next show. Now, 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, though, is the aesthetics of your setup: if it looks too simple, people will be unimpressed and they might figure out that you are actually a worthless DJ.

It doesn’t 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’ve made a large strip, with the ports in certain fixed places, and you’ve 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’re able to fit all of the cords onto the strip or not. If not, the aesthetics are ruined, and you’ll have to start all over again.


  • The first line has two integers $2\leq n\leq 5 \cdot 10^5$ and $1\leq m\leq 5 \cdot 10^5$, the number of ports on the strip and the number of wires.

  • The second line has $n$ integers $0\leq x_1< \dots < x_ n\leq 10^9$, the positions of the sockets.

  • The third line has $m$ integers $l_1, \dots , l_ m$, the lengths of the wires, with $1\leq l_ i\leq 10^9$.


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

Sample Input 1 Sample Output 1
4 4
0 2 3 7
1 3 3 7
Sample Input 2 Sample Output 2
3 4
0 1 2
10 10 10 10

Please log in to submit a solution to this problem

Log in