26607번 - 시로코와 은행털기

문제

블루아카이브에 있는 아비도스 고등학교 학생, 스나오오카미 시로코는 은행 터는 것을 자주 시뮬레이션한다.

게임의 마스코트, 스나오오카미 시로코이다.

어느 날, 정말로 은행을 털어보고 싶다는 생각이 든 시로코는 은행을 털 준비를 하기 시작했다. 우선, 은행 터는 것을 함께 할 팀을 만들 것인데, 경쟁을 뚫고 마지막까지 살아남은 $n$명 중에서 최종적으로 $k$명을 팀원으로 선발할 계획이다. 지원자들은 각각 힘과 스피드 수치 $a,ドル $b$가 주어지는데, 쟁쟁한 경쟁을 뚫고 살아남은 자들답게 $a+b$가 모두 동일하다.

$i$번째 팀원으로 선발한 사람의 능력치가 각각 $a_{i},ドル $b_{i}$라 할 때, 그 팀의 종합 능력치는 $(\sum\limits_{i=1}^{k} a_{i})\times(\sum\limits_{i=1}^{k} b_{i})$이다. 팀의 능력치를 최대화하게 지원자들을 선발하려 할 때 그때 그 팀의 능력치를 출력하라.

입력

첫 번째 줄에 사람의 수 $n$와 뽑을 인원 $k,ドル 그리고 힘과 스피드 수치의 합 $x$가 공백으로 구분되어 주어진다.

그 다음줄부터 $n$개의 줄에는 각 사람들이 지닌 힘과 스피드 능력치 $a$ $b$가 주어진다.

출력

팀의 능력치를 최대화하게 인원을 선발할 때, 그 팀의 능력치를 출력하라.

제한

• 1ドル \leq n \leq 80$
• 1ドル \leq k \leq n$
• 1ドル \leq x \leq 200$
• 0ドル \leq a, b$

힌트