oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

tvshows Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

tvshows.html

Problem Description

Karl the Invoker is tired of people making fun of him for only knowing ten spells, so he has started to learn new spells to expand his repertoire. Of course, memorising incantations is a rather tedious and boring task, so Karl amuses himself in his spare time by watching television. Naturally Karl cannot watch shows in the day since he is busy training, so he records all the shows in a day to be watched later. However, because of his busy, irregular timetable, Karl doesn't have time to watch all the shows he wants. Thus, he has asked you to help him schedule his television watching for his maximum satisfaction.

Each day, Karl records at least zero television programs. Each television program lasts L time units and provides S satisfaction to Karl when watched. Karl has a varying amount of T time units each day to watch television. He can watch any number of shows recorded on or before the current day as long as the total L of the shows he watches does not exceed T.

Given the maximum time allowances of T time units for each day, as well as the daily list of shows each lasting L time units and providing S satisfaction, over N days, determine the maximum satisfaction that Karl can derive from his television watching in one day.

Input

The first line of input will consist of 1 integer, N

The rest of the intput is divided into N sections presented like so:

The first line of the ith section will consist of 2 integers, Ti and Mi

Subsequent M lines will consist of 2 integers each, representing the L and S for each show on the ith day.

Output

Output a single integer indicating the maximum satisfaction possible in one day within the given time period.

Limits

Subtask 1 (9%): N = 1; all L = 1; 0 ≤ M, T ≤ 10000

Subtask 2 (11%): N = 1; 0 ≤ M, T ≤ 1000; 1 ≤ L ≤ 1000

Subtask 3 (13%): 1 ≤ N ≤ 10; all L = 1; 0 ≤ M, T ≤ 1000

Subtask 4 (17%): 1 ≤ N ≤ 10; all 0 ≤ T ≤ 10 are equal; 0 ≤ M ≤ 1000; 1 ≤ L ≤ 10

Subtask 5 (19%): 1 ≤ N ≤ 10; 0 ≤ M, T ≤ 10; 1 ≤ L ≤ 10

Subtask 6 (31%): 1 ≤ N ≤ 100; 0 ≤ M, T ≤ 100; 1 ≤ L ≤ 100

Subtask 7 (0%): Sample Testcase

For all testcases, 0 ≤ S ≤ 1000 and the maximum satisfaction possible in one day will not exceed the size of a 32-bit integer.

Sample Input

3

2 1
3 5

3 2
2 2
2 4

4 3
1 1
2 2
1 2

Sample Output

7

Explanation

On Day 3, Karl watches the (3, 5) show from Day 1 and the (1, 2) show from Day 3. This gains him 7 satisfaction.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
19111s32MBMinimum
211111s32MBMinimum
313111s32MBMinimum
417111s32MBMinimum
519111s32MBMinimum
631111s32MBMinimum
7011s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o tvshows -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.