문제
2차원 평면에 점이 N개 주어진다. i번째 점은 (xi, yi)에 있다. 이 때, 다음 쿼리를 처리하는 프로그램을 작성하자.
1 a: 모든 점들 중, axi + yi의 최댓값을 출력한다.
2 x y: (x, y)에 점을 하나 추가한다.
입력
첫 번째 줄에 점의 개수를 의미하는 자연수 N과 쿼리의 개수 Q가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)
두 번째 줄부터 N개의 줄에 점의 위치 (xi, yi)가 주어진다. (-109 ≤ xi, yi ≤ 109)
그 다음 줄부터 Q개의 줄에 각 쿼리의 번호 q와, 1번이라면 a가, 2번이라면 x y가 정수로 주어진다. (-109 ≤ a ≤ 109, -109 ≤ x, y ≤ 109)
출력
1번 쿼리에 대해, 모든 점들 중, axi + yi의 최댓값을 출력한다.
예제
5 7
-2 2
-1 1
3 3
5 6
7 -5
1 -10
1 -2
2 4 8
1 0
1 2
2 8 0
1 10
22
6
8
16
80
로그인해야 코드를 작성할 수 있어요.