시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 18 2 2 12.500%

문제

 

되팔렘 민혁이는 매일 아침 물건 시세를 알아보기 위해 온갖 덕질 사이트들을 돌아다닌다. 평소와 같이 시세를 조사하던 민혁이는 손에 들린 핸드폰이 뜨거워짐을 느꼈지만 신경을 쓰지 않았고 이윽고 핸드폰이 폭발하고 말았다!

정신을 차린 민혁이에게는 초능력이 생겼는데 중고로운 평화나라에 올라온 물건을 보면 내일 이 물건을 되팔 때 가격을 알 수 있게 된 것이다. 신이 난 민혁이는 이 초능력의 이름을 되팔렘의 눈이라고 불렀다.

중고로운 평화나라의 탈덕 게시판에서는 덕질을 그만둔 사람들이 물건을 파는데 자신의 일부와도 같았던 덕질용품들을 한꺼번에 팔아 덕질과의 연을 끊도록 되어있다.

진정한 되팔렘으로 거듭난 민혁이는 덕질을 그만둔 사람들에게서 그들의 덕질용품을 모두 사들여 비싼 값에 되팔려고 한다. 과연 어떤 사람들에게서 물건을 사들여야 엄청난 이득을 내는 되팔렘이 될 수 있을까?

입력

첫번째 줄에는 오늘 되팔렘이 가진 자본금 C가 입력된다. (0 < C ≤ 230)

다음 줄에는 두개의 정수가 입력되는데 하나는 덕질용품의 갯수 N과 물건들을 팔려고 하는 사람들의 수 P다. (0 < N ≤ 500), (0 < P ≤ 50000)

이후 N개의 줄에서는 두 개의 정수가 입력되는데 각 줄에는 i 번째 덕질용품의 현재 가격인 ai와 되팔렘의 눈으로 알아낸 이 물건의 내일 가격 ti 이다.  (1 ≤ i ≤ N) (i는 품번이라고 부른다)

마지막으로는 P개의 줄이 입력되는데 각 줄에는 사람이 파는 덕질용품들의 정보다. 처음에는 이 사람이 가진 덕질용품의 종류 수 R이 입력된다. 그 뒤로는 이 사람이 파는 덕질용품의 품번 sj와 갖고 있는 갯수 qj가 입력된다. (1 ≤ j ≤ R)

출력

되팔렘이 내일 낼 수 있는 최대의 이익을 출력한다.

예제 입력 1

500
4 6
10 15
8 6
20 15
12 12
3 1 6 2 7 3 8
3 3 8 1 10 2 4
3 4 10 2 5 1 10
2 1 4 2 4
1 3 2
2 4 3 2 1

예제 출력 1

52

예제 입력 2

200000000
5 30
2800 3500
1400 4800
2900 2800
500 3800
3300 4700
2 2 13 4 15
4 4 1 1 22 3 17 5 22
1 3 2
1 3 6
4 1 11 2 5 3 7 5 15
1 5 1
4 2 26 1 21 3 8 5 26
2 3 5 2 26
4 2 30 4 12 3 7 5 14
3 3 8 2 20 5 3
1 5 30
2 1 29 3 3
5 3 3 1 20 5 26 4 9 2 25
3 1 2 2 16 3 5
2 5 5 4 26
5 2 18 5 10 4 18 1 12 3 30
3 2 5 3 27 5 4
4 3 2 4 8 1 20 2 6
3 2 14 1 1 4 22
5 2 23 3 26 1 27 5 3 4 6
1 2 16
4 1 13 4 10 2 23 5 2
1 1 14
1 2 20
1 3 14
2 3 21 1 22
1 2 27
3 5 24 1 26 3 13
5 4 15 3 3 2 21 1 5 5 16
4 2 22 5 1 4 10 1 30

예제 출력 2

2168800
W3sicHJvYmxlbV9pZCI6IjM4MTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0MThcdWQzMTRcdWI4MTgiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgY2xhc3M9XCJpbWctcmVzcG9uc2l2ZVwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC91c2VydXBsb2FkXC9SaWRkbGVyXC8yMDE2MDkwM1wvOTUxYWU1YWI5M2ZkMzkwMzk4ODkyZWY4MDg4MmJhMjUuanBnXCIgXC8+PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI0MThcdWQzMTRcdWI4MTggXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YjllNFx1Yzc3YyBcdWM1NDRcdWNlNjggXHViYjNjXHVhYzc0IFx1YzJkY1x1YzEzOFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWJjZjRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzYyOFx1YWMxNiBcdWIzNTVcdWM5YzggXHVjMGFjXHVjNzc0XHVkMmI4XHViNGU0XHVjNzQ0IFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJjY1x1YjJlNC4mbmJzcDtcdWQzYzlcdWMxOGNcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzJkY1x1YzEzOFx1Yjk3YyBcdWM4NzBcdWMwYWNcdWQ1NThcdWIzNTggXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YzE5MFx1YzVkMCBcdWI0ZTRcdWI5YjAgXHVkNTc4XHViNGRjXHVkM2YwXHVjNzc0IFx1YjcyOFx1YWM3MFx1YzZjY1x1YzlkMFx1Yzc0NCBcdWIyOTBcdWFmMDhcdWM5YzBcdWI5Y2MgXHVjMmUwXHVhY2JkXHVjNzQ0IFx1YzRmMFx1YzljMCBcdWM1NGFcdWM1NThcdWFjZTAgXHVjNzc0XHVjNzNkXHVhY2UwJm5ic3A7XHVkNTc4XHViNGRjXHVkM2YwXHVjNzc0IFx1ZDNlZFx1YmMxY1x1ZDU1OFx1YWNlMCBcdWI5ZDBcdWM1NThcdWIyZTQhPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YzJlMFx1Yzc0NCBcdWNjMjhcdWI5YjAgXHViYmZjXHVkNjAxXHVjNzc0XHVjNWQwXHVhYzhjXHViMjk0IFx1Y2QwOFx1YjJhNVx1YjgyNVx1Yzc3NCBcdWMwZGRcdWFjYmNcdWIyOTRcdWIzNzAgXHVjOTExXHVhY2UwXHViODVjXHVjNmI0IFx1ZDNjOVx1ZDY1NFx1YjA5OFx1Yjc3Y1x1YzVkMCBcdWM2MmNcdWI3N2NcdWM2MjggXHViYjNjXHVhYzc0XHVjNzQ0IFx1YmNmNFx1YmE3NCBcdWIwYjRcdWM3N2MgXHVjNzc0IFx1YmIzY1x1YWM3NFx1Yzc0NCBcdWI0MThcdWQzMTQmbmJzcDtcdWI1NGMmbmJzcDtcdWFjMDBcdWFjYTlcdWM3NDQgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWFjOGMgXHViNDFjIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjMmUwXHVjNzc0IFx1YjA5YyBcdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNzc0IFx1Y2QwOFx1YjJhNVx1YjgyNVx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDQgXHViNDE4XHVkMzE0XHViODE4XHVjNzU4IFx1YjIwOFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWJkODhcdWI4MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzkxMVx1YWNlMFx1Yjg1Y1x1YzZiNCBcdWQzYzlcdWQ2NTRcdWIwOThcdWI3N2NcdWM3NTggXHVkMGM4XHViMzU1IFx1YWM4Y1x1YzJkY1x1ZDMxMFx1YzVkMFx1YzExY1x1YjI5NCZuYnNwO1x1YjM1NVx1YzljOFx1Yzc0NCBcdWFkZjhcdWI5Y2NcdWI0NTQgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YmIzY1x1YWM3NFx1Yzc0NCBcdWQzMGNcdWIyOTRcdWIzNzAmbmJzcDtcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzdjXHViZDgwXHVjNjQwXHViM2M0IFx1YWMxOVx1YzU1OFx1YjM1OCBcdWIzNTVcdWM5YzhcdWM2YTlcdWQ0ODhcdWI0ZTRcdWM3NDQgXHVkNTVjXHVhZWJjXHViYzg4XHVjNWQwIFx1ZDMxNFx1YzU0NCBcdWIzNTVcdWM5YzhcdWFjZmNcdWM3NTggXHVjNWYwXHVjNzQ0IFx1YjA0YVx1YjNjNFx1Yjg1ZCBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljNFx1YzgxNVx1ZDU1YyBcdWI0MThcdWQzMTRcdWI4MThcdWM3M2NcdWI4NWMgXHVhYzcwXHViNGVkXHViMDljIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWIzNTVcdWM5YzhcdWM3NDQgXHVhZGY4XHViOWNjXHViNDU0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YzVkMFx1YWM4Y1x1YzExYyBcdWFkZjhcdWI0ZTRcdWM3NTggXHViMzU1XHVjOWM4XHVjNmE5XHVkNDg4XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWMwYWNcdWI0ZTRcdWM1ZWMmbmJzcDtcdWJlNDRcdWMyZmMgXHVhYzEyXHVjNWQwIFx1YjQxOFx1ZDMxNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWNmY1x1YzVmMCBcdWM1YjRcdWI1YTQgXHVjMGFjXHViNzhjXHViNGU0XHVjNWQwXHVhYzhjXHVjMTFjIFx1YmIzY1x1YWM3NFx1Yzc0NCBcdWMwYWNcdWI0ZTRcdWM1ZWNcdWM1N2MgXHVjNWM0XHVjY2FkXHViMDljIFx1Yzc3NFx1YjRkZFx1Yzc0NCBcdWIwYjRcdWIyOTQgXHViNDE4XHVkMzE0XHViODE4XHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2MjRcdWIyOTggXHViNDE4XHVkMzE0XHViODE4XHVjNzc0IFx1YWMwMFx1YzljNCBcdWM3OTBcdWJjZjhcdWFlMDggQ1x1YWMwMCZuYnNwO1x1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4mbmJzcDsoMCAmbHQ7IEMgJmxlOyAyPHN1cD4zMDxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MThcdWIyOTRcdWIzNzAgXHVkNTU4XHViMDk4XHViMjk0IFx1YjM1NVx1YzljOFx1YzZhOVx1ZDQ4OFx1Yzc1OCBcdWFjMmZcdWMyMTggTlx1YWNmYyZuYnNwO1x1YmIzY1x1YWM3NFx1YjRlNFx1Yzc0NCBcdWQzMTRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc1OCBcdWMyMTggUFx1YjJlNC4mbmJzcDsoMCAmbHQ7IE4gJmxlOyA1MDApLCZuYnNwOygwICZsdDsgUCAmbGU7IDUwMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWMxMWNcdWIyOTQmbmJzcDtcdWI0NTAmbmJzcDtcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwJm5ic3A7XHVjNzg1XHViODI1XHViNDE4XHViMjk0XHViMzcwIFx1YWMwMSZuYnNwO1x1YzkwNFx1YzVkMFx1YjI5NCBpIFx1YmM4OFx1YzlmOCBcdWIzNTVcdWM5YzhcdWM2YTlcdWQ0ODhcdWM3NTggXHVkNjA0XHVjN2FjIFx1YWMwMFx1YWNhOVx1Yzc3OCZuYnNwO2E8c3ViPmk8XC9zdWI+XHVjNjQwIFx1YjQxOFx1ZDMxNFx1YjgxOFx1Yzc1OCBcdWIyMDhcdWM3M2NcdWI4NWMgXHVjNTRjXHVjNTQ0XHViMGI4IFx1Yzc3NCBcdWJiM2NcdWFjNzRcdWM3NTggXHViMGI0XHVjNzdjIFx1YWMwMFx1YWNhOSZuYnNwO3Q8c3ViPmk8XC9zdWI+Jm5ic3A7XHVjNzc0XHViMmU0LiAmbmJzcDsoMSAmbGU7IGkgJmxlOyBOKSAoaVx1YjI5NCBcdWQ0ODhcdWJjODhcdWM3NzRcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0KTxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWNcdWIyOTQgUFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQmbmJzcDtcdWM3ODVcdWI4MjVcdWI0MThcdWIyOTRcdWIzNzAgXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkMzBjXHViMjk0IFx1YjM1NVx1YzljOFx1YzZhOVx1ZDQ4OFx1YjRlNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyZTQuIFx1Y2M5OFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWM3NzQgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWMwMFx1YzljNCBcdWIzNTVcdWM5YzhcdWM2YTlcdWQ0ODhcdWM3NTggXHVjODg1XHViOTU4IFx1YzIxOCBSXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4mbmJzcDtcdWFkZjggXHViNGE0XHViODVjXHViMjk0IFx1Yzc3NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkMzBjXHViMjk0IFx1YjM1NVx1YzljOFx1YzZhOVx1ZDQ4OFx1Yzc1OCBcdWQ0ODhcdWJjODgmbmJzcDtzPHN1Yj5qPFwvc3ViPlx1YzY0MCBcdWFjMTZcdWFjZTAgXHVjNzg4XHViMjk0IFx1YWMyZlx1YzIxOCBxPHN1Yj5qPFwvc3ViPlx1YWMwMCZuYnNwO1x1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4mbmJzcDsoMSAmbGU7IGogJmxlOyBSKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjQxOFx1ZDMxNFx1YjgxOFx1Yzc3NCBcdWIwYjRcdWM3N2MgXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwXHVjNzU4IFx1Yzc3NFx1Yzc3NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzgxMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNoYXJlcyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBhIHN1Y2Nlc3NmdWwgYnVzaW5lc3MgbWFuIHdobyB1c2VzIHRvIGludmVzdCBzb21lIG1vbmV5IGluIHRoZSBzaGFyZXMgbWFya2V0LiBBcyBhIHN1Y2Nlc3NmdWwgbWFuIHlvdSBtYW5hZ2UgYSBuZXR3b3JrIG9mIHdlbGwgcHJlcGFyZWQgYXNzaXN0YW50cyB0aGF0IGNhbiBhc3N1cmUgeW91IHRoZSB2YWx1ZXMgb2YgdGhlIHNoYXJlcyBmb3IgdGhlIG5leHQgZGF5LiBFYWNoIGRheSB5b3UgaGF2ZSBhIGNhcGl0YWwgdGhhdCB5b3UgY2FuIHNwZW5kIGluIHRoZSBtYXJrZXQgYWNjb3JkaW5nIHRvIHlvdXIgYXNzaXN0YW50cyBzdWdnZXN0aW9ucy4gSW4gYWRkaXRpb24sIHlvdSBjYW4gb25seSBidXkgcGFja3Mgb2Ygc2hhcmVzIGZyb20gc2V2ZXJhbCBzYWxlc21lbi48XC9wPlxyXG5cclxuPHA+WW91ciBnb2FsIGlzIHRvIHNlbGVjdCB3aGljaCBwYWNrcyBzaG91bGQgYmUgYm91Z2h0IGluIG9yZGVyIHRvIG1heGltaXplIHRoZSBwcm9maXRzIHdpdGhvdXQgZXhjZWVkaW5nIHRoZSBhbW91bnQgb2YgY2FwaXRhbCB5b3UgaGF2ZS4gT2J2aW91c2x5LCB5b3UgY2FuIGJ1eSBlYWNoIHBhY2sgb25seSBvbmNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG1heGltdW0gY2FwaXRhbCBDIHRoYXQgeW91IGNhbiBpbnZlc3QgKDAgJmx0OyBDICZsZTsgMjxzdXA+MzA8XC9zdXA+KS4gVGhlIG5leHQgbGluZSBoYXMgdHdvIGludGVnZXJzLCB0aGUgbnVtYmVyIG9mIHRvdGFsIHNoYXJlcyBOICgwICZsdDsgTiAmbGU7IDUwMCkgYW5kIHRoZSBudW1iZXIgb2YgcGFja3MgUCAoMCAmbHQ7IFAgJmxlOyA1MDAwMCkuIEVhY2ggb25lIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBkZXNjcmliZSB0aGUgTiBzaGFyZXMuIEVhY2ggbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgYTxzdWI+aTxcL3N1Yj4gYW5kIHQ8c3ViPmk8XC9zdWI+IHJlcHJlc2VudGluZyB0aGUgY3VycmVudCBwcmljZSBhbmQgdGhlIGV4cGVjdGVkIHByaWNlIGZvciB0aGUgbmV4dCBkYXkgb2YgdGhlIGl0aCBzaGFyZSAoMSAmbGU7IGkgJmxlOyBOKSwgcmVzcGVjdGl2ZWx5LiBGaW5hbGx5LCB0aGUgZm9sbG93aW5nIFAgbGluZXMgY29udGFpbiB0aGUgaW5mb3JtYXRpb24gb2YgdGhlIHBhY2tzLCBvbmUgcGVyIGxpbmUuIEZvciBlYWNoIGxpbmUsIHRoZSBmaXJzdCBpbnRlZ2VyIFIgcmVwcmVzZW50cyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBzaGFyZXMgdGhhdCBjb250YWlucyB0aGlzIHBhY2suIFRoZW4gZm9yIGVhY2ggc2hhcmUgdHlwZSB5b3UgaGF2ZSB0d28gaW50ZWdlcnMgczxzdWI+ajxcL3N1Yj4gYW5kIHE8c3ViPmo8XC9zdWI+ICgxICZsZTsgaiAmbGU7IFIpLCB3aGVyZSBzPHN1Yj5qPFwvc3ViPiBpcyB0aGUgaWQgb2YgdGhlIGp0aCBzaGFyZSBhbmQgcTxzdWI+ajxcL3N1Yj4gaXMgdGhlIHF1YW50aXR5IG9mIHRoZSBqdGggc2hhcmUgaW4gdGhpcyBwYWNrLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkFuIGludGVnZXIgdGhhdCBpbmRpY2F0ZXMgdGhlIG1heGltdW0gZXhwZWN0ZWQgcHJvZml0IGZvciB0aGUgbmV4dCBkYXkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d