When adding p_i + A_{k+1} to C, there is a problem because A_{k+1} is already used in p_i. Therefore you need to start with A_{k+2}, but A_{k+2} need not exist (k = n-1 for example). Fortunately k can not be n - 1 (not hard to see). The argument that C has at least n - k + m elements needs more justification. it is not very hard, but can be tricky to get it correct.
Another side comment: We can not assume A_1 < A_2 < ... < A_n. Since A_1 through A_k is chosen by a specific rule we can not assume the order of them. It is always safe to assume A_{k+1} < A_{k+2} < ... < A_n though, and it is enough for your proof.
I really like your proof. Great job.