다리 놓기

강 서쪽에 N개의 도시, 동쪽에 M개의 도시가 있다. 서쪽 도시는 위에서 아래로 1번부터 N번, 동쪽 도시는 위에서 아래로 1번부터 M번까지 번호가 붙어 있다. 강을 가로지르는 다리를 놓으려 하는데, 다리끼리 교차하면 안 된다.

서쪽 i번 도시와 동쪽 j번 도시를 연결하는 다리를 놓을 계획이 C개 있을 때, 교차하지 않게 놓을 수 있는 다리의 최대 수를 구하시오.