시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNjI0XHViMjk4IFx1YjQxOFx1ZDMxNFx1YjgxOFx1Yzc3NCBcdWFjMDBcdWM5YzQgXHVjNzkwXHViY2Y4XHVhZTA4IENcdWFjMDAmbmJzcDtcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuJm5ic3A7KDAgJmx0OyBDICZsZTsgMjxzdXA+MzA8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjNzg1XHViODI1XHViNDE4XHViMjk0XHViMzcwIFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWIzNTVcdWM5YzhcdWM2YTlcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWFjZmMmbmJzcDtcdWJiM2NcdWFjNzRcdWI0ZTRcdWM3NDQgXHVkMzE0XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHVjMjE4IFBcdWIyZTQuJm5ic3A7KDAgJmx0OyBOICZsZTsgNTAwKSwmbmJzcDsoMCAmbHQ7IFAgJmxlOyA1MDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHVjMTFjXHViMjk0Jm5ic3A7XHViNDUwJm5ic3A7XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCZuYnNwO1x1Yzc4NVx1YjgyNVx1YjQxOFx1YjI5NFx1YjM3MCBcdWFjMDEmbmJzcDtcdWM5MDRcdWM1ZDBcdWIyOTQgaSBcdWJjODhcdWM5ZjggXHViMzU1XHVjOWM4XHVjNmE5XHVkNDg4XHVjNzU4IFx1ZDYwNFx1YzdhYyBcdWFjMDBcdWFjYTlcdWM3NzgmbmJzcDthPHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWI0MThcdWQzMTRcdWI4MThcdWM3NTggXHViMjA4XHVjNzNjXHViODVjIFx1YzU0Y1x1YzU0NFx1YjBiOCBcdWM3NzQgXHViYjNjXHVhYzc0XHVjNzU4IFx1YjBiNFx1Yzc3YyBcdWFjMDBcdWFjYTkmbmJzcDt0PHN1Yj5pPFwvc3ViPiZuYnNwO1x1Yzc3NFx1YjJlNC4gJm5ic3A7KDEgJmxlOyBpICZsZTsgTikgKGlcdWIyOTQgXHVkNDg4XHViYzg4XHVjNzc0XHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk3OFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjXHViMjk0IFBcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzc0Jm5ic3A7XHVjNzg1XHViODI1XHViNDE4XHViMjk0XHViMzcwIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0IFx1ZDMwY1x1YjI5NCBcdWIzNTVcdWM5YzhcdWM2YTlcdWQ0ODhcdWI0ZTRcdWM3NTggXHVjODE1XHViY2Y0XHViMmU0LiBcdWNjOThcdWM3NGNcdWM1ZDBcdWIyOTQgXHVjNzc0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjMDBcdWM5YzQgXHViMzU1XHVjOWM4XHVjNmE5XHVkNDg4XHVjNzU4IFx1Yzg4NVx1Yjk1OCBcdWMyMTggUlx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuJm5ic3A7XHVhZGY4IFx1YjRhNFx1Yjg1Y1x1YjI5NCBcdWM3NzQgXHVjMGFjXHViNzhjXHVjNzc0IFx1ZDMwY1x1YjI5NCBcdWIzNTVcdWM5YzhcdWM2YTlcdWQ0ODhcdWM3NTggXHVkNDg4XHViYzg4Jm5ic3A7czxzdWI+ajxcL3N1Yj5cdWM2NDAgXHVhYzE2XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFjMWNcdWMyMTggcTxzdWI+ajxcL3N1Yj5cdWFjMDAmbmJzcDtcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuJm5ic3A7KDEgJmxlOyBqICZsZTsgUik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI0MThcdWQzMTRcdWI4MThcdWM3NzQgXHViMGI0XHVjNzdjIFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWM3NzRcdWM3NzVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM4MTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTaGFyZXMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgYSBzdWNjZXNzZnVsIGJ1c2luZXNzIG1hbiB3aG8gdXNlcyB0byBpbnZlc3Qgc29tZSBtb25leSBpbiB0aGUgc2hhcmVzIG1hcmtldC4gQXMgYSBzdWNjZXNzZnVsIG1hbiB5b3UgbWFuYWdlIGEgbmV0d29yayBvZiB3ZWxsIHByZXBhcmVkIGFzc2lzdGFudHMgdGhhdCBjYW4gYXNzdXJlIHlvdSB0aGUgdmFsdWVzIG9mIHRoZSBzaGFyZXMgZm9yIHRoZSBuZXh0IGRheS4gRWFjaCBkYXkgeW91IGhhdmUgYSBjYXBpdGFsIHRoYXQgeW91IGNhbiBzcGVuZCBpbiB0aGUgbWFya2V0IGFjY29yZGluZyB0byB5b3VyIGFzc2lzdGFudHMgc3VnZ2VzdGlvbnMuIEluIGFkZGl0aW9uLCB5b3UgY2FuIG9ubHkgYnV5IHBhY2tzIG9mIHNoYXJlcyBmcm9tIHNldmVyYWwgc2FsZXNtZW4uPFwvcD5cclxuXHJcbjxwPllvdXIgZ29hbCBpcyB0byBzZWxlY3Qgd2hpY2ggcGFja3Mgc2hvdWxkIGJlIGJvdWdodCBpbiBvcmRlciB0byBtYXhpbWl6ZSB0aGUgcHJvZml0cyB3aXRob3V0IGV4Y2VlZGluZyB0aGUgYW1vdW50IG9mIGNhcGl0YWwgeW91IGhhdmUuIE9idmlvdXNseSwgeW91IGNhbiBidXkgZWFjaCBwYWNrIG9ubHkgb25jZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBtYXhpbXVtIGNhcGl0YWwgQyB0aGF0IHlvdSBjYW4gaW52ZXN0ICgwICZsdDsgQyAmbGU7IDI8c3VwPjMwPFwvc3VwPikuIFRoZSBuZXh0IGxpbmUgaGFzIHR3byBpbnRlZ2VycywgdGhlIG51bWJlciBvZiB0b3RhbCBzaGFyZXMgTiAoMCAmbHQ7IE4gJmxlOyA1MDApIGFuZCB0aGUgbnVtYmVyIG9mIHBhY2tzIFAgKDAgJmx0OyBQICZsZTsgNTAwMDApLiBFYWNoIG9uZSBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgZGVzY3JpYmUgdGhlIE4gc2hhcmVzLiBFYWNoIGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIGE8c3ViPmk8XC9zdWI+IGFuZCB0PHN1Yj5pPFwvc3ViPiByZXByZXNlbnRpbmcgdGhlIGN1cnJlbnQgcHJpY2UgYW5kIHRoZSBleHBlY3RlZCBwcmljZSBmb3IgdGhlIG5leHQgZGF5IG9mIHRoZSBpdGggc2hhcmUgKDEgJmxlOyBpICZsZTsgTiksIHJlc3BlY3RpdmVseS4gRmluYWxseSwgdGhlIGZvbGxvd2luZyBQIGxpbmVzIGNvbnRhaW4gdGhlIGluZm9ybWF0aW9uIG9mIHRoZSBwYWNrcywgb25lIHBlciBsaW5lLiBGb3IgZWFjaCBsaW5lLCB0aGUgZmlyc3QgaW50ZWdlciBSIHJlcHJlc2VudHMgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgc2hhcmVzIHRoYXQgY29udGFpbnMgdGhpcyBwYWNrLiBUaGVuIGZvciBlYWNoIHNoYXJlIHR5cGUgeW91IGhhdmUgdHdvIGludGVnZXJzIHM8c3ViPmo8XC9zdWI+IGFuZCBxPHN1Yj5qPFwvc3ViPiAoMSAmbGU7IGogJmxlOyBSKSwgd2hlcmUgczxzdWI+ajxcL3N1Yj4gaXMgdGhlIGlkIG9mIHRoZSBqdGggc2hhcmUgYW5kIHE8c3ViPmo8XC9zdWI+IGlzIHRoZSBxdWFudGl0eSBvZiB0aGUganRoIHNoYXJlIGluIHRoaXMgcGFjay48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BbiBpbnRlZ2VyIHRoYXQgaW5kaWNhdGVzIHRoZSBtYXhpbXVtIGV4cGVjdGVkIHByb2ZpdCBmb3IgdGhlIG5leHQgZGF5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==