광고 수익

가짜 뉴스 기사를 만드는 동기 중 하나는 돈이다. 사이트를 찾은 방문자에게 광고를 보여 주거나 방문자가 광고를 클릭하면 수익이 생긴다. 수수께끼 같거나 놀랍거나 자극적인 이야기는 독자를 많이 끌어모으기 때문에, 가짜 뉴스의 제목은 흔히 과장되고 모호하다("당신은 믿지 못할 것이다 ...").

온라인 광고는 보통 두 가지 형태다. 노출형 광고는 광고를 보여 주기만 해도 광고주가 사이트에 돈을 낸다. 브랜드를 각인시키는 것이 목적이다. 클릭형 광고는 방문자가 광고를 클릭할 때만 광고주가 돈을 낸다. 클릭 중 일부가 지금이든 나중이든 구매로 이어진다고 보는 것이다. 온라인 광고 단가는 노출이나 클릭 한 번에 몇 센트인 것부터 클릭 한 번에 $100에 이르는 것까지 있다. (클릭 한 번에 $100을 내는 광고주는 집단소송 전문 변호사다.)

클릭형과 노출형 광고의 목록, 그리고 방문자마다 무엇을 보았고 무엇을 클릭했는지 담은 기록이 주어진다. 이 가짜 뉴스 사이트가 번 돈을 계산하라.

첫째 줄에 파일에 들어 있는 데이터 집합의 개수 $K$가 주어진다. $K \ge 1$이다. 이어서 아래 형식의 데이터 집합이 $K$개 주어진다.

각 데이터 집합의 첫째 줄에는 정수 $n$, $v$가 주어진다. $n$은 이 사이트의 고객인 광고의 개수로 $2 \le n \le 1000$이고, $v$는 사이트 방문자 수로 $0 \le v \le 1000$이다.

다음 $n$개 줄에는 광고 $i$를 나타내는 정수 $d_i$, $p_i$가 주어진다. $d_i$는 0 또는 1이다. 1이면 노출형 광고라서 보여 주기만 해도 사이트가 돈을 받는다. 0이면 클릭형 광고라서 방문자가 클릭해야만 사이트가 돈을 받는다. $p_i$는 그 광고의 지급액으로 $1 \le p_i \le 1000$이다. 노출형은 노출 한 번마다, 클릭형은 클릭 한 번마다 지급된다.

다음 $v$개 줄에는 방문자 $j$를 나타내는 정수 $a_{j,1}$, $a_{j,2}$, $c_j$가 주어진다. 앞의 두 수는 방문자에게 보여 준 광고 두 개이며, 서로 다르고 1 이상 $n$ 이하다. $c_j \in \{0, 1, 2\}$는 방문자가 클릭한 광고를 나타낸다. 0이면 아무것도 클릭하지 않았고, 1이면 $a_{j,1}$을, 2이면 $a_{j,2}$를 클릭했다. 방문자가 노출형 광고를 클릭할 수도 있는데, 이때 사이트는 추가로 돈을 받지 않는다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 그 데이터 집합의 번호다. 다음 줄에 사이트가 받는 지급액의 합을 출력한다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.