Buy One Get One Free

A farmer is buying bales of hay online and finds a special deal: for every bale of high quality hay that he buys, he may claim one bale of low quality hay for free — provided the free bale is strictly smaller than the one he bought.

Formally, a purchased high quality bale of size $A$ lets him take one low quality bale of size $B$ for free, but only if $B < A$. Every bale size satisfies $1 \le \text{size} \le 1{,}000{,}000$. The farmer only cares about the number of bales, not their quality.

You are given the sizes of $N$ high quality bales ($1 \le N \le 10{,}000$) and $M$ low quality bales ($1 \le M \le 10{,}000$). He may buy any high quality bale by itself without claiming a free bale, but he can never buy a low quality bale directly: every low quality bale he obtains must come for free through the deal, and each high quality bale he buys can grant at most one free low quality bale.

Find the maximum total number of bales the farmer can obtain.

• Line 1: two space-separated integers $N$ and $M$.
• Lines $2 \dots N+1$: line $i+1$ contains a single integer, the size of the $i$-th high quality bale.
• Lines $N+2 \dots N+M+1$: line $i+N+1$ contains a single integer, the size of the $i$-th low quality bale.

• Line 1: the maximum total number of bales the farmer can obtain.

Buying every high quality bale is always safe, since an extra purchase never lowers the total. The goal is then to pair as many low quality bales as possible with distinct high quality bales, where each pair must have the low quality bale strictly smaller. Sorting both lists and greedily matching each low quality bale with the smallest high quality bale that still exceeds it maximizes the number of free bales.

For example, with high quality bales of sizes $6, 1, 3$ and low quality bales of sizes $1, 5, 3, 4$: buying the size-$6$ bale frees the size-$3$ low quality bale, and buying the size-$3$ bale frees the size-$1$ low quality bale; the size-$1$ bale can free nothing. That yields $3 + 2 = 5$ bales in total.