excellent proof, needs correction in some places.

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
I really like your proof. Great job.