Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1156. Giant Screen
Олимпиадные задачи на английском языке| 06/12/2008 | Занятие 10 (задачи NEERC 2008) (G) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
You are working in Advanced Computer Monitors (ACM), Inc. The company is building and selling
giant computer screens that are composed from multiple smaller screens. Your are responsible for design
of the screens for your customers.
Customers order screens of the specified horizontal and vertical resolution in pixels and a specified
horizontal and vertical size in millimeters. Your task is to design a screen that has a required resolution
in each dimension or more, and has required size in each dimension or more, with a minimal possible
price. The giant screen is always built as a grid of monitors of the same type. The total resolution, size,
and price of the resulting screen is simply the sum of resolutions, sizes, and prices of the screens it is
built from.
You have a choice of regular monitor types that you can order and you know their resolutions, sizes, and
prices. The screens of each type can be mounted both vertically and horizontally, but the whole giant
screen must be composed of the screens of the same type in the same orientation. You can use as many
screens of the chosen type as you need.
Input
The first line of the input file contains four integer numbers `r_h`, `r_v`, `s_h`, and `s_v` (all from 100 to `10\ 000`
inclusive) – horizontal and vertical resolution and horizontal and vertical size of the screen you have to
build, respectively. The next line contains a single integer number `n` (`1\ ≤\ n\ ≤\ 100`) – the number of
different screen types available to you. The next n lines contain descriptions of the available screen types.
Each description occupies one line and consists of five integer numbers – `r_{h,i}`, `r_{v,i}`, `s_{h,i}`, `s_{v,i}`, `p_i` (all from
100 to `10\ 000` inclusive), where first four numbers are horizontal and vertical resolution and horizontal
and vertical size of `i`-th screen type, and `p_i` is the price.
Output
Write to the output file a single integer – the minimal price of the specified giant screen.
Sample Input 1
1024 1024 300 300 3 1024 768 295 270 200 1280 1024 365 301 250 1280 800 350 270 210
Sample Output 1
250
Sample Input 2
2400 2000 800 700 3 1024 768 295 270 200 1280 1024 365 301 250 1280 800 350 270 210
Sample Output 2
1260
